Applied Algorithms (Spring 2021)

Applied Algorithms (Spring 2021)

Teaching Mode (Hybrid and Online)

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 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)

Instructors

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.

Course Description

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
- Recurrences
- Sorting and order statistics
- Heap and Priority Queue
- Divide-and-Conquer algorithms
- Greedy algorithms
- Dynamic programming algorithms
- Amortized analysis
- Graph algorithms
- Flow in networks

Required Textbook

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.

Resources

  • 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

Week

Contents

1
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.
2
Module 1: Algorithm Analyses and Asymptotic notations; Reading 2.2, 3. Jan. 26 lectures notes and video. Jan. 28 lecture notes and video.
3
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.
4
Module 3: Master Theorem; Reading: 4.4, 4.5. Feb. 9 lecture notes and video. Feb. 11 lectures notes (Quicksort) and video.
5
Module 4: Sorting algorithms; Reading: 7, 8, 9.2. Feb. 16 no class (IU Wellness Day). Feb. 18 lecture notes and video.
6
Module 5: Greedy Algorithms; Reading: 16. Feb. 23 lecture notes and video. Feb. 25 lecture notes and video.
7
Module 6: Dynamic programming Algorithms; Reading: 15
8 Midterm Exam
9 Module 7: Heap; Reading 6
10
Module 8: Amortized Analyses; Reading 17, 19
11
Module 9: Graph algorithms: connectivity problems; Reading 22
12 Module 10: Graph algorithms: Shortest distance problems; Reading 24, 25.2
13 Module 11: Graph algorithms: minimum spanning tree; Reading 23
14 Module 12: Graph algorithms: flow in network; Reading 26
15
TBD
16 Final exam

Course Summary:

Date Details Due