EECS 281 Data Structures and Algorithms
EECS 281
Data Structures and Algorithms
Mr. Marcus Darden
Dr. Michał Dereziński
Dr. Héctor Garcia-Ramirez
Dr. David Paoletti
Fall 2021
mailto:
Other Staff
Teaching Assistants
• Clare Speer (GSI)
• Haizhong Zheng (GSI)
• Murali Mohan (GSI)
• Omar Al-Ejel (GSI)
• Wenfei Tang (GSI)
• Aaron Weldy
• Aasher Akhlaque
• Abbas Fattah
• Aidan Wilber-Gauthier
• Akshaya Jagadeesh
• Anna Wang
• Annie Li
• Austin McCulley
2
• Blake King
• Danielle Digiovine
• Elanor Tang
• Elenor Markus
• Jacqueline Dimonte
• Jason Deal
• Jillian Lew
• Joe Richards
• Jonathan Alpert
• Ke Liu
• Kriti Moogala
• Marie Phillips
• Matthew Kondamudi
• Megan Coden
• Mert Gerdan
• Michael Jecmen (AG)
• Nicholas Anason
• Nikhil Kanamarla
• Nish Patel
• Nishka Muzumdar
• Reina Ades
• Reyna Wood
• Ryan Brown
• Srihari Srinivasan
• Surya Cruz
• Undarmaa Ganbaatar
Course Staff
3
Potatobot (Piazza)
Image copyright: www.instructables.com
Course Weekly Schedule
Lectures
• Tuesday / Thursday
• 9am-6pm, 6 lectures
• Important announcements
in lectures
Labs
• See the Schedule of
Topics on Canvas
• No labs during the first
week
4
All lectures and labs cover the same material
Important Dates
• NOW: 281 Crash Course: posted on
YouTube, see next slide
• Midterm: Thursday 10/21, 7-9:20pm
• Final: Wednesday 12/15, 8-10:20am
6
281 Crash Course
• We used to do one long session (in
person) and record it, but we made
separate videos during COVID
• Watch one of the first 3, and the last 2:
– Visual Studio Tutorial
– Xcode Tutorial
– Visual Studio Code Debugging and WSL
– Project 0 Tutorial
– Makefiles Tutorial
8
Syllabus
• Please read the syllabus on Canvas
• This lecture summarizes:
– Course policies (prereqs, collaboration, honor
code, office hours, etc.)
– Assignments and grades
– Tips for success
– Organization of Topics
9
Prerequisites
• We enforce prerequisites: 203 and 280
– If you enrolled in EECS 281 before receiving
grades in EECS 203 or 280 that do not allow you
to enroll in EECS 281, you must drop 281
• For EECS 203, we count Math 465 and 565
(graph theory, combinatorics, etc)
• Per Departmental Policy, grad students
cannot register for, or audit, EECS courses
below 400-level (including EECS 281)
10
Topic Preparedness Self-survey
• There is a short survey on Canvas
(Quizzes, under Practice Quizzes)
– Multiple choice
– Assessment of prerequisite material
– Will not affect your course grade
– Gives you practice on the Canvas “Quiz” tool
• Will help you decide whether you are
adequately prepared for EECS 281
12
Policy on Collaboration
• All work submitted for Projects and Exams
must be your own
• You may use source code provided by
EECS 281 instructors
• You may reuse YOUR OWN CODE if you
are retaking EECS 281
• If you use other code and try to obscure it,
we have automated ways to detect that
13
Policy on Collaboration
• Do not show your project code to others
– Do not post code on Piazza
– Do not use open online repositories (github,
etc.)
• Do not share project test files; only submit
your own test files
• When in doubt, ask us (using Piazza or
come to office hours)
14
Honor Code
• Read Honor Code (link is on Canvas)
• Please know that we take this very
seriously
• We automatically check electronic
submissions for violations of Honor Code
• We (teaching staff) are the ‘traffic cops’.
Honor Council is the ‘court of law’
15
OK to use Wikipedia, Google, etc.?
• Yes, it is – to understand algorithms and
data structures covered in lecture
– External sources must be mentioned in labs &
projects for credit assignment reasons
– We do not accept external references to
justify answers on labs, exams, etc.
– Don’t copy+paste from GitHub!
16
Getting Help & Contacting Us
• For urgent & personal issues
– goes to all instructors and TAs
• For really personal issues –
– Make an appointment
• http://cppreference.com
• http://www.cplusplus.com/
• http://piazza.com
– Do not post code from lab and project solutions
– Do not ask if your solution is correct
– You can post anonymously to other students
(but we will know your name)
– Students can answer questions of other students
– Instructors endorse good answers
• Please “close” your questions once answered
17
mailto:
http://cppreference.com/
http://www.cplusplus.com/
http://piazza.com/
Office Hours
• Come prepared with specific questions
– Conceptual is fine
– If code-specific, please have input that your program does work
with, and input that it does not
• Attend soon after the project is assigned and get
conceptual questions answered before you start coding
• Sign up at http://eecs.help
• Please respect other students
– Ask one question, then move to back of line
– Can listen to other student’s questions, as long as not personal in
nature
– If you hear someone that has the same issue that you already
solved, feel free to tell them, in general, about the problem and
solution!
18
http://eecs.help/
Office Hours
• Staff Office Hours Etiquette
– Will be posted on the Google Calendar by the end of the first
week
– Please respect course staff availability, as TA’s are students
too
• Professor Office Hours Etiquette
– Always available during scheduled office hours
– Sometimes available for quick questions (1-2 min) when office
door is open
– Can schedule time outside of posted OH for personal matters
– Not available when office door is closed
– Not available during undergrad advising hours
19
Office Hours Queue
• Come to Proffice Hours!
– Join the Google Meet for any question that doesn’t
need you to show us code
– This discussion helps everyone in the room
– Listen to other students’ questions
• Don’t join an 80-person queue instead of
Proffice hours meet!
• Join the help queue when you need 1-on-1 help
– Code won’t compile
– Need to talk about your course grade
20
Grading
• Grading Policy
– 20% Labs (10)
– 40% Projects (4)
– 20% Midterm Exam
– 20% Final Exam
22
What Guarantees that I Pass?
• Achieve minimal competency
• If you earn ALL OF:
(>= 50% on Exams)
AND (>= 55% on Projects)
AND (>= 75% on Labs)
• You will pass this course
• A total of 68, with 30% projects, 100% labs
and 90% exams is NOT PASSING
23
Labs (20%)
• 10 lab assignments
• Can work with other students
• Submit via Gradescope, electronically via
Canvas, and/or autograder machine
• Late submissions: must contact us via
BEFORE THE
DUE DATE and provide documentation
(extreme medical/personal)
24
mailto:
Lab Times
• You do not have to attend the lab that
you’re enrolled in
• We would like you to attend the same
lab time each week
– Make contacts and consistent
partnerships
26
Written Portion
• Every lab has a “written” problem
– Pre-COVID, this was done on paper, during
lab; now submitted via Gradescope
– This is practice for the exams
– It is graded by effort
• To understand what you’re supposed to be
doing for the written problem you must
attend lab
28
Lab Groups
• No need to “register” groups
• All students must submit all parts
individually to receive points!
• There’s a “written” portion done during lab
– This is practice for the exams
– It is graded by effort
29
Projects (40%)
• 4 projects
• Individual work
• Submitted electronically to autograder
– Details to follow
• Approximately 2 weeks per project
• Late submissions: USE LATE DAYS
WISELY (see “Policy on Deadlines”)
31
Policy on Deadlines
• Autograder: 2 Late Days per semester
• Use them as you want
• Project 0 late days are “free”, use them for
practice!
– Before any “real” assignment is due, everyone
will be reset to 2 late days remaining
• Example: if a Project was due Tuesday, today is
Thursday; you didn’t submit yesterday = 2 late
days to submit today (submitting 2 days late)
32
Projects (40%)
• C++ (International C++17 Standard)
– https://en.wikipedia.org/wiki/C++17
• CAEN Linux Computing Environment
– g++ (GCC) 6.2.0
• Beware if you are doing development in
any other environment
– May compile/run perfectly for you, then not
even compile on the autograder
33
https://en.wikipedia.org/wiki/C++17
Autograder
• We will grade projects with an autograder
– Correctness, timing and memory usage
• Immediate feedback on most test cases
• ~3 submissions per day
– 3 for Projects 1-3; 4 for Project 4
– +1 submit per day for finding enough bugs!
– More in Spring (due to double speed)
• We grade the best submission before the
deadline (each project specification and the AG
FAQ tells how to request last instead of best)
34
Before Debugging Help
• Before getting help debugging, you should
have:
– Submitted to the autograder
• Included test files of your own
• The autograder will tell you if your own test file
reveals your solution as buggy!
– Tested all provided examples using valgrind
– Found as small a test as possible that reveals
your bug
35
36
• Red tests failed (wrong output or exit status)
• Blue tests are over time and/or memory
Submission time vs. score
*data from
EECS 281,
Fall 2013
37
Exams (40%)
• Midterm Exam (20%)
• Final Exam (20%)
• Will test your understanding of material and
problem-solving skills
• Both a multiple choice section and a long
answer section
• Must notify instructor 2 weeks ahead if conflict
• Cannot miss exam without documented serious
medical or personal emergency
38
Curving
• If necessary, we will change the points
required to pass the exams
– Will only make it easier to pass, never harder
• May also adjust overall grades
– May adjust grades upward if needed, never down
• You can calculate what you need on the final
to pass
– Have to pass both exams and projects
• Let us know of any concerns early
40
Will Solutions Be Posted?
• Yes – for labs (see Canvas after the due
date)
• No
– For in-class exercises (some yes, some no)
– For projects
– For exams
• Midterm solutions may be outlined in class
• Clarifications on Piazza and office hours
41
Lectures
• You can print out (or use digital version)
lecture notes, and must go over them
– Before the lecture – to prepare questions
– After the lecture – to make sure everything was
clear and review for exam
• Take notes during lecture!
– Studies demonstrate that students taking notes
longhand remember more and have a deeper
understanding of the material
– https://www.scientificamerican.com/article/a-
learning-secret-don-t-take-notes-with-a-laptop/
42
https://www.scientificamerican.com/article/a-learning-secret-don-t-take-notes-with-a-laptop/
Lectures
• Not all material presented in lecture will
appear in the lecture slides
– Explanations on a tablet
– Additional practice questions
• If you are not following lecture material,
don’t wait until just before the exam
– Ask questions, attend office hours
43
What Do I Need To Do To Succeed?
• Be serious and organized, stay sharp
• Allocate sufficient time for this course
• Be proactive
• Prioritize tasks — don’t waste your time
• Don’t get stuck, do ask for help
• Practice writing code by hand! To
prepare for the exams, treat Labs,
projects, etc. as exam questions
44
Computing CARES
• View their website here:
http://www.eecs.umich.edu/eecs/about/articl
es/2015/Computing_CARES.html
• 281 Video:
45
http://www.eecs.umich.edu/eecs/about/articles/2015/Computing_CARES.html
How Many Hours Per Week?
• It varies widely, based on
– How well you remember EECS 280 material
• Makefiles, library functions, debugging,
using headers properly, etc.
– Same with EECS 203 material
• Counting, induction, complexity, summations,
graphs
– Following our directions
– How well you plan?
– Do you need to redo things?
46
Study Groups
• Generally, a great idea
– You will not overlook important material
– Someone can fill you in on a lecture you
missed
• Downside: your project code may look
similar and will attract extra scrutiny
47
Useful tools
• Automated compilations
– make
• Editors for “power users”
– Vim, Emacs
• Version control system
– Git (https://git-scm.com/), (https://gitlab.umich.edu),
Mercurial (https://www.mercurial-scm.org)
– Subversion (https://subversion.tigris.org/)
http://en.wikipedia.org/wiki/Subversion_(software)
48
https://git-scm.com/
https://gitlab.umich.edu/
https://www.mercurial-scm.org/
https://subversion.tigris.org/
http://en.wikipedia.org/wiki/Subversion_(software)
Making Copies of your Code
• Suppose you DON’T do any of the
following things (the first 3 which we
suggested):
– Upload to the autograder
– Upload to CAEN to test building with g++
– Upload your code to the gitlab server
– Copy your files to a flash drive
• Then your computer dies…
49
Don’t let This be You
50
IDE
• One platform allows the use of multiple
tools through a single interface
– Text editor
• Many have tooltip popups for method parameters
• Some detect errors while typing
– Advanced code browsing (look up method
definitions, jump directly to them from a call)
– Project management/make
– Compiler, debugger, profiler
– Some include version control
51
Partial List of IDEs
• NetBeans (free)
– netbeans.org
– C++, Java, etc.
• Eclipse (free)
– eclipse.org
– C++, Java, etc.
• VS Code (free)
• Visual Studio 20XX,
Enterprise or Community
– Enterprise edition
– Community edition
– C++, C#
– PC only
• Xcode (free)
– apple.com
– C++, Swift, Objective-C
– Mac only
52
*Need a separate g++ compiler
such as Cygwin or Min-GW
Multiple Platforms*Proprietary
http://www.netbeans.org
http://www.eclipse.org
https://e5.onthehub.com/WebStore/ProductsByMajorVersionList.aspx?cmi_cs=1&cmi_mnuMain=bdba23cf-e05e-e011-971f-0030487d8897&ws=118e6889-eb9b-e011-969d-0030487d8897&vsro=8
https://www.visualstudio.com/vs/community/
http://www.dreamspark.com/
Plotting Tools
• Useful for plotting algorithm statistics
– Runtimes
– Memory Usage
– Other parameters
• Gnuplot (installed on CAEN Unix)
– http://www.gnuplot.info/
• Google Sheets
• Excel (installed on CAEN Windows)
– http://www.usd.edu/trio/tut/excel/
• Matlab (installed on CAEN Windows)
– http://www.math.ufl.edu/help/matlab-tutorial/
53
http://www.wikipedia.com/
http://www.gnu.org/software/diffutils/
http://www.sgi.com/tech/stl
Pre-Midterm: Foundational
Skills & Techniques
• Complexity analysis of algorithms
• Building blocks – elementary algorithms
& data structures
– Sorting, searching, stacks and queues, priority
queues (+ possibly more)
• Implementation in C++17 using STL
– How to be efficient, what to avoid
• Time measurement and optimization
• Algorithmic problem-solving
• Examples for how to select the best algorithm for
a problem
54
After the Midterm:
Sophisticated Algorithms
• Binary search trees (dictionaries)
• Hashing and hash tables
• Graph algorithms
• Algorithm types
– Divide-and-conquer
– Greedy
– Dynamic programming
– Backtracking and branch-and-bound
55
Data Structures and ADTs
• Need a way to store and organize data in
order to facilitate access and modifications
• An abstract data type (ADT) defines a
collection of valid operations and their
behaviors on stored data
– e.g., insert, delete, access
– ADTs define an interface
• A data structure provides a concrete
implementation of an ADT
56
Algorithms
• An algorithm is a well-defined procedure
that solves a computational problem
– Transforms given input data into desired
output or answer
• “Recipe” or “Set of Directions”
• Algorithms are tools for solving problems
– Sort a list of data, find the shortest path
between classes, pack as many boxes as
possible in a delivery truck
57
Analyzing Data Structures and
Algorithms
• When designing algorithms and DSs, we
care about:
– How long does an operation take (# of steps)?
– How much space is used?
• Predict answers before running the code
– Avoid wasting time on bad designs
• Complexity analysis answers these
questions relative to the size/quantity of
input data
58
Algorithm Engineering
• For a given application, is it better to use:
– Algorithm A or algorithm B?
– Data structure X or data structure Y?
– Often you can tell before writing any code
– Sometimes you need an empirical comparison
– Sometimes the answer is surprising
• For a given piece of code:
– Where is the bottleneck?
– How do you speed it up?
59
Algorithm Exercise
1. Write this function
2. How many multiplications will it take if
size = 1 million?
//REQUIRES: in and out are arrays with size elements
//MODIFIES: out
//EFFECTS: out[i] = in[0] *…* in[i-1] *
// * in[i+1] *…* in[size-1]
void f(int *out, const int *in, int size);
60
Developing Your Skills
• Problem-solving
• Algorithm analysis
• Software development
• Practice, repetition, and rewriting
– Building skills
• Memorization
– Not necessarily rote!
– Required for speed in programming
– Building blocks and processes
63
Be a Good Software Engineer!
• When is a given technique appropriate?
– Pointers (or references), classes, STL
• Good code versus bad code
– Modular, concise, readable, debuggable
• Functional robustness
– Input checking, assertions, etc.
• Code reuse: less work, less debugging
• Write code to avoid and minimize bugs
64