OVERVIEW
Through this course, you will learn the two fundamental themes in computer programs: the data structures that represent the program state, and algorithms that manipulate the data structures for solving computational problems. The two themes interleave throughout the lectures.
This course will cover:
-
Essential data structures, including stacks, queues, lists, trees, and graphs.
-
Fundamental algorithms and their complexities, including sorting, search, hashing, and graph algorithms.
|
Important
|
Offline questions and discussion will happen through Piazza.
|
what’s new
-
8/11: website is online.
time & location
1.30 — 2.45 PM, Tue and Thu, Electrical Engineering Bldg 170
prerequisites
-
Proficiency in C programming (Purdue equivalence: ECE 264 Advanced C Programming [Fall'16])
-
Set up an ECN account; being able to login over SSH; using gcc; basic *Nix commands.
staff
-
Instructor: Prof. Felix Xiaozhu Lin <xzl@purdue.edu>, office: EE324B
-
Graduate teaching assistant (GTA): Xiangyu Qu <qu27@purdue.edu>
-
Undergraduate teaching assistants (UTAs):
-
Tyler Baumgartner <baumgar6@purdue.edu>
-
Omar Abouhussein <oabouhus@purdue.edu>
-
Abhay Sasidharan <asasidh@purdue.edu>
-
Rui Wang <wang3420@purdue.edu>
-
office hours
| Day | Time | Place | Staff |
|---|---|---|---|
Mon |
10.30 — 12pm |
EE206 |
Rui (UTA) |
Mon |
1.30 — 3.00pm |
EE207 |
Omar (UTA) |
Tue |
2.45 — 3.30pm |
EE324B |
Felix (Instructor) |
Wed |
10.00 — 11.30am |
EE207 |
Tyler (UTA) |
Wed |
4.00 — 5.30pm |
EE206 |
Xiangyu (GTA) |
Thu |
2.45 — 3.30pm |
EE324B |
Felix (Instructor) |
Fri |
12.00 — 1.30pm |
EE206 |
Abhay (UTA) |
See EE206/207 schedule.
On-demand appointment is possible. Send Prof. Lin <xzl@purdue.edu> an email.
text book
The "official" textbook: Algorithms in C, Parts 1-5 (Bundle): Fundamentals, Data Structures, Sorting, Searching, and Graph Algorithms (3rd Edition), Robert Sedgewick, Addison-Wesley, 2001, ISBN-10: 0201756080 Amazon
The one I liked: Introduction to Algorithms, 3rd Edition, Cormen, Leiserson, Rivest, Stein. Also known as "CLRS". This book is informative, fun, and easy to read! This book is NOT required by this course. Yet, I strongly encourage students to read some of the chapters and consider owning a copy.
SCHEDULE
Subject to (minor) adjustment.
| WEEK | DATE | TOPIC | READING | ASSIGN. | DUE |
|---|---|---|---|---|---|
0.Tue |
2019-08-20 |
Introduction [slides] |
Ch 1 (pp 3-26) |
survey link |
|
0.Thu |
2019-08-22 |
Analysis of Algorithms [slides] |
Ch 2 (pp 27-66); CLRS Ch3 |
||
1.Tue |
2019-08-27 |
Analysis (cont’d); Bubble Sort [slides] |
Ch 6 (pp 253-300); CLRS Ch3 |
survey due |
|
1.Thu |
2019-08-29 |
Basic Sorts: Insertion; Selection [slides] |
Ch 6 (pp 261-265); CLRS Ch2 |
||
2.Tue |
2019-09-03 |
Locality; Shell Sort [slides] |
Ch 6 (pp 273-279) |
hw1 due |
|
2.Thu |
2019-09-05 |
Abstract Date Types [slides] |
Ch 4 (pp 127-186) |
||
3.Tue |
2019-09-10 |
Abstract Date Types; Stacks [slides] |
Ch 4 (pp 127-150) |
hw2 due |
|
3.Thu |
2019-09-12 |
Recursion [slides] |
Ch 5 (pp 187-207) |
p1 link |
|
4.Tue |
2019-09-17 |
Queues; Lists [slides] |
Ch 4 (pp 153-161) Ch 9 (pp 383-392) Ch 3 (pp 90-108) |
||
4.Thu |
2019-09-19 |
Binary Trees [slides] |
Ch 5 (pp 216-240) |
p1 ms1 |
|
5.Tue |
2019-09-24 |
Binary Search Trees; Midterm1 Review [slides] |
Ch 12 (pp 502-520) |
hw3 due |
|
5.Wed |
2019-09-25 |
Midterm Exam1 (evening) ; 8 — 9pm; CL50 224 | Essence | Sample | Sample Sol | Sol |
|||
5.Thu |
2019-09-26 |
Binary Search Trees; Balancing BST [slides] |
Ch 13 (pp 557-560) |
||
6.Tue |
2019-10-01 |
Balancing BST (cont’d) |
p2 link |
hw4 due; p1 final |
|
6.Thu |
2019-10-03 |
Midterm1 Review |
Ch 13 (pp 557-560) |
||
7.Tue |
2019-10-08 |
OCTOBER BREAK: NO CLASS |
|||
7.Thu |
2019-10-10 |
Heap [slides] |
Ch 9 (pp 361-403); Ch 7 (pp 303-335) |
p2 ms1; hw5 due |
|
8.Tue |
2019-10-15 |
CANCELED: (makeup for evening exam1) |
|||
8.Thu |
2019-10-17 |
Divide and Conquer; Quick Sort [slides] |
Ch 7 (pp 303-335) |
hw6 due |
|
9.Tue |
2019-10-22 |
Quick Sort; Merge Sort [slides] |
Ch 8 (pp 335-361) |
||
9.Thu |
2019-10-24 |
Linear Time Sorting — Counting Sort [slides] |
|||
10.Tue |
2019-10-29 |
Bucket Sort and Radix Sort [slides] |
Ch 10 (pp 403-437) |
p2 final |
|
10.Thu |
2019-10-31 |
Linear and Binary Search [slides] |
Ch 2 (pp 53-59) |
hw7 due |
|
11.Tue |
2019-11-05 |
Hashing and Hash Tables [slides] |
Ch 14 (pp 574-603) |
p3 link |
|
11.Thu |
2019-11-07 |
Midterm Exam2 (evening); 8 — 9pm; PHYS 114 | Solution Graphs slides Graph Traversal [slides] |
Ch 17 |
hw8 due |
|
12.Tue |
2019-11-12 |
Graph: Shortest Paths [slides] |
Ch 21 (pp 265-352) |
p3 ms1 |
|
12.Thu |
2019-11-14 |
Graph: Minimum Spanning Trees [slides] |
Ch 20 (pp 219-264) |
hw9 due |
|
13.Tue |
2019-11-19 |
Graph: Maximum Network Flow [slides] |
Ch 22 (pp 352-396) |
p3 ms2 |
|
13.Thu |
2019-11-21 |
Potpourri [slides] |
|||
14.Tue |
2019-11-26 |
CANCELED: (makeup for evening exam2) |
|||
14.Thu |
2019-11-28 |
Thanksgiving: NO CLASS |
|||
15.Tue |
2019-12-03 |
Dynamic Programming (useful but not req’d for exam) [slides] |
CLRS; Chap 15 |
hw10 due; p3 final |
|
15.Thu |
2019-12-05 |
Course Review [slides] |
Final: Thu 12/12
GRADE
The breakdown will be:
| Total | 100% |
|---|---|
Homework |
15% |
Project |
20% |
Quizzes, Participation |
5% |
Two midterms |
30% (15% each) |
Final Exam |
30% |
The instructor reserves the right to adjust the final grades.
homeworks
One time per week. The download links will be made available on the syllabus. You have one week to finish each homework. Homework is due at the beginning of the class on the due date. Missing two or more homeworks: one letter penalty in the final grade.
quizzes
Several in-lecture; never announced beforehand; may happen in any lecture. The purpose is to 1) promote course participation and 2) briefly review the course materials.
projects
There will be three projects. For each project, you have roughly two weeks to complete. Log in ECN servers to work on code and submit the code electronically there. More details will come soon.
One-time deadline extension
Each student gets one penalty-free 12 hour extension (can be used by the student for any one of the projects)
-
One-time use (cannot be split among multiple projects)
-
50% penalty for buying one more 12 hour extension token
To request for using the extension: go here. Email requests sent to the instructor or TA will be ignored.
milestones
A project may have milestones, which are often lightweight deliverables that describe the progress of the project (e.g. one paragraph describing your approach to the problem).
-
Milestones that are turned in on time will be considered for partial credits if the final project submission does not meet the basic correctness or performance requirements.
-
In case an deadline extension is granted to the entire class, only the students who have turned in all the existing milestones of the project on time will receive the extension.
policy of late submissions
Late submissions, unless there is a deadline extension, will be either rejected without grading or penalized.
However, we may consider late submissions for the following cases:
-
The student has a DRC letter that explicit grants extra time.
-
Medical condition that is proved by a hospital letter signed by a doctor.
-
Family emergency that is acknowledged by Office of the Dean of Students.
-
An off-campus job interview, as proved by an invite letter from the interviewing company.
-
The student must notify the instructor or TA at least 48 hours before the deadline.
-
-
A failure in the Purdue’s IT infrastructure that is beyond the student’s control. To make such a case, a student must present evidence showing the following two things both have happened:
-
A failure in the ECN server or the Purdue campus network has happened.
-
The student’s submission would have completed if the failure did not exist.
-
The following events are NOT legitimate reasons:
-
The student’s difficulty in login or using a ECN server or workstation.
-
The student’s personal disk quota is full.
-
The student’s difficulty in connecting to a ECN server (e.g. due to apartment network outrage), unless ECN is proved responsible.
-
The student’s difficulty in using the submission program or client program, e.g. thinlinc.
-
A failure of the student’s personal computer.
-
Any loss of program or data, unless ECN is proven responsible.
|
Note
|
What to do in case of the last-minute IT failures?
|
STATEMENTS
accommodations
Absence: If have to miss a lecture, notify the instruction at least one week in advance.
Make-up exams are only granted based on Purdue’s official rules. The instructor is also willing to consider events that are critical to the student’s future career, such as job interviews.
disability
If you are a student registered with the Disability Resource Center and you are in need of academic accommodations, please see me during my office hours listed on the syllabus as soon as possible. If you have an Accommodation Letter from the Disability Resource Center, we need to meet during my office hours to discuss your needs. See office hours, location, and phone number above.
emergency
In the event of a major campus emergency, course requirements, deadlines and grading percentages are subject to changes that may be necessitated by a revised semester calendar or other circumstances. In such an event, information will be provided through this syllabus.