Applied Algorithms (Spring 2021)
Teaching Mode (Hybrid and Online)
UPDATE: Starting March 23, the lectures will be in classroom PV 167 and on Zoom. The classroom has a capacity of 25 students. Please attend in-person if and only if your visa requires in-person attendance.
- If your last name starts with a letter from A to M, please attend the Tuesday lectures in person.
- If your last name starts with a letter from N to Z, please attend the Thursday lectures in person.
The lectures will be online for the first 75% of the course (Zoom) and they will be simultaneously in-person and online for the last 25% of the course. If you need the in-person credit, sign up for the hybrid lecture section 37486. If you don't care about the in-person credit, sign up for the online lecture section 9635. Students in any of the sections will be allowed to attend the in-person lectures in the later part of the course. All of the labs will be conducted online.
Lecture: Tue. and Thu. 11:30A-12:45P in PV 167 and on Zoom
Lab: Friday 1:45P-2:35P or 3:00P-3:50P on Zoom
(the lab zoom has the same password as the lecture)
If you have a question about grades, please direct your question to the teaching assistant responsible for students whose first letter of their last name is in the range given below.
- Jeremy Siek (jsiek), office hours: Tuesdays and Thursdays 4:30-5:30pm on zoom (same password as lecture)
- Chao-Hong Chen (chen464), office hours: Tuesdays 1-3pm on the Lab Zoom, student grades: A to G
- Bhumika Agrawal (bagrawal), office hours: Wednesdays 10am - 12pm on the Lab Zoom, student grades: H to M.
- Rupesh Deshmukh (rddeshmu), office hours: Mondays 3-5pm on the Lab Zoom, student grades: N to R.
- Stephen Karukas (skarukas), office hours: Wednesdays 1-3pm on the Lab Zoom, student grades: S to Z.
The objective of the course is to study the principles for the design and analysis of efficient algorithms and their implementations. Prior programming experience in C/C++, Java or Python is expected. The important themes that will be covered by this course include
- Basic principles for algorithm design
- Analysis of algorithms and asymptotic notations
- Sorting and order statistics
- Heap and Priority Queue
- Divide-and-Conquer algorithms
- Greedy algorithms
- Dynamic programming algorithms
- Amortized analysis
- Graph algorithms
- Flow in networks
Introduction to Algorithms, Third Edition. Author(s): Cormen, Leiserson, Rivest, and Stein; ISBN-13: 978-0262033848 [CLRS]
Late Homework Policy
You may submit homework and labs up to one week late with a 10% reduction in the grade for that assignment.
- Slack Workspace link (for questions both during and after class)
- Autograder link (for turning in programming assignments)
- IntelliJ IDE link (download the Community Edition)
- Rationale for using half-open intervals is here
- Books for learning Java
- Head First Java, 2nd Edition.
- Core Java Volume I – Fundamentals, 11th Edition.
Schedule of Topics
||Module 0: Algorithm warm-up; Reading Chapter 1, 2.1. Jan. 19 lecture notes and video. Jan. 21 lecture notes and video. Jan. 22 lab notes.
||Module 1: Algorithm Analyses and Asymptotic notations; Reading 2.2, 3. Jan. 26 lectures notes and video. Jan. 28 lecture notes and video.
||Module 2: Divide-and-Conquer algorithms; Reading: 2.3, 4.1, 4.2. Feb. 2 lecture notes and video. Feb. 4 lecture notes and video.
||Module 3: Master Theorem; Reading: 4.4, 4.5. Feb. 9 lecture notes and video. Feb. 11 lectures notes (Quicksort) and video.
||Module 4: Sorting algorithms; Reading: 7, 8, 9.2. Feb. 16 no class (IU Wellness Day). Feb. 18 lecture notes and video.
||Module 5: Greedy Algorithms; Reading: 16. Feb. 23 lecture notes and video. Feb. 25 lecture notes and video.
||Module 6: Dynamic programming Algorithms; Reading: 15. March 2 lecture notes and video. March 4 lecture notes and video.
|8||Midterm Review (March 9) notes and video, Midterm Exam (March 11)|
|9||Module 7: Heap; Reading 6. March 16 lecture notes and video. March 18 lecture notes and video.|
||Module 8: Amortized Analyses, Binomial Heaps; Reading 17, 19. March 23 lecture notes and video. March 25 lecture notes and video.|
||Module 9: Graph algorithms: connectivity problems; Reading 22. March 30 lecture notes and video. April 1 lecture notes and video.|
|12||Module 10: Graph algorithms: Shortest distance problems; Reading 24, 25.2. April 6 lecture notes and video. April 8 lecture notes and video.|
|13||Module 11: Graph algorithms: minimum spanning tree; Reading 23. April 13 lecture notes and video. April 15 lecture notes and video.|
|14||Module 12: Graph algorithms: flow in network; Reading 26. April 20 lecture notes and video.|
||Review for the Final Exam (no lab this week). Lecture notes. April 27 video. April 29 video.|
|16||Final exam: May 6 (Thursday) 7:45-9:45 a.m.|
The syllabus page shows a table-oriented view of the course schedule, and the basics of course grading. You can add any other comments, notes, or thoughts you have about the course structure, course policies or anything else.
To add some comments, click the "Edit" link at the top.