Basic Algorithms, Summer 2024, CSCI-UA.0310- 001
· Class Meetings: Tuesdays and Thursdays,
2:10-4:15 pm, online via Zoom (see Brightspace for class link)
· Midterm Exam: July 2, 2024, 2:10-4:15
pm, Zoom link on Brightspace
· Final Exam: Aug 15, 2:10-4:15 pm,
Zoom link on Brightspace
· Instructor: Areeba Ikram; student
drop-in hour Thursday 4:15 pm-5:15 pm, Zoom link on Brightspace, additionally
by appointment
· Tutors and tutoring hours (Zoom links
are on Brightspace):
· TBA
Reviews several
important algorithms, with emphasis on correctness and efficiency. The topics
covered include solving recurrence equations, sorting algorithms, binary search
trees, partitioning, graphs, spanning trees, shortest paths, connectivity,
depth-first and breadth-first search, dynamic programming, and
divide-and-conquer techniques. The somewhat ambitious plan is to cover (most
of) chapters 1-4, 6-8, 12, 15, 16, 22-25, 30, 31, 34 of [CLRS] (see below).
At least one year of
experience with a high-level language such as Pascal, C, C++, or Java;
familiarity with recursive programming methods and data structures (arrays,
pointers, stacks, queues, linked lists, binary trees).
· Introduction to Algorithms by Thomas
H. Cormen, Charles E. Leiserson,
Ronald L. Rivest, and Cliff Stein, published by MIT Press. Our main textbook.
· Algorithm Design by Jon Kleinberg and
Eva Tardos, Published by Pearson.
· Lecture
Slides for Algorithm Design by Kevin Wayne, distributed by Pearson. See the
Brightspace page for accessible versions of these slides.
Notes, assignments, and other course materials will be posted on the course Brightspace page.
|
Week |
Dates |
Topics |
Read
and watch before class |
|
1 |
May 23, May 25 |
Intro, logistics, insertion sort, run time analysis, Big-O notation, merge sort, Analysis of merge sort, Quick Sort |
CLRS §1, §2.1, §2.2; Insertion sort video and demo (click INS) CLRS §2.3,3; Merge Sort video and demo (click MER); Big-O video CLRS §2.3, 4.3-4.6, 7; Quick Sort video and demo (click QUI) |
|
2 |
May 30, June 1
|
Finishing Quick Sort; Karatsuba's algorithm, Closest pair in the plane |
CLRS §7, KT §5, CLRS §33.4 |
|
3 |
June 6, June 8
|
Median and order statistics in linear time; Lower bound for comparison sort |
CLRS §9, CLRS §8.1 |
|
4 |
June 13, June 15 |
Counting sort, Radix sort; Dynamic Programming: Fibonacci Numbers, Rod Cutting Problem |
CLRS §8.2, §8.3, CLRS §15.1 |
|
5 |
June 20, June 22 |
Dynamic Programming: Longest Common Subsequence, Knapsack |
CLRS §15.4, visualization CLRS §15.3-4; Demaine's video lecture |
|
6 |
June 27, Jun 29 |
Catch-up/review Midterm 1 |
|
|
7 |
July 6
(No class July 4 - Independence Day) |
Greedy: Activity selection (aka interval scheduling) Greedy - Huffman Code |
CLRS §16.1-2, 6 first minutes of video on priority queues; CLRS §16.3 |
|
8 |
July 11, July 13
|
Greedy - Huffman Code, Graphs, BFS |
CLRS §16.3, CLRS §22.1-22.2, adj list and adj matrix visualization, visualization |
|
9 |
July 18, July 20 |
DFS, edge classification, detecting acyclic graphs, Topological sort, strongly connected components |
CLRS §22.3; video
CLRS §22.4,22.5 |
|
10 |
July 25, July 27 |
Finishing SCC; Minimum Spanning Tree MST safe edge theorem, Kruskal's algorithm Prim's algorithm |
CLRS §23.1; demo
CLRS §23.2 |
|
11 |
August 1, August 3
|
Dijkstra's SSSP algorithm, Floyd-Warshall APSP algorithm, Computability, Wang tiling, the halting problem is uncomputable |
CLRS §24.3 and video, CLRS §25.2, CLRS §34 |
|
12 |
August 8, August 10 |
P vs. NP, NP-completeness, Vertex Cover, Independent set, 3SAT, reductions, approximating Vertex Cover |
CLRS §34, 35 |
|
13 |
August 15 |
Final Exam |
There will be weekly homework
assignments. We prefer homework submissions typeset in LaTeX (you might want to
use the Overleaf templates) or Word. You are encouraged to insert scanned
figures or illustrations. Scanned handwritten submissions will only be graded
if neatly written and perfectly legible. Honors questions will be graded
but will not affect your grade. Submission is through Gradescope.
The written
assignments will require rigorous solutions which give clear and straightforward explanations.
Each answer will be judged on the explanation’s clarity, correctness, and
conciseness. A design of an algorithm requires proof of correctness and proof
of runtime for full credit, along with a clear explanation of the
algorithm. You will receive zero credit for the answer if you write
pseudocode without any explanation.
The tentative grade
split is 5% participation, 40% homework, 25% midterm, and 30% final exam.
Late submissions of
homework solutions will be graded with a 20% penalty per day of late
submission. Solutions will not be graded if submitted later than 48 hours after
the specified deadline.
Please review the
departmental academic
integrity policy.
We strongly encourage
you to discuss assignments with your peers. However, all work that you submit
must be your own. You must list all discussions you had. For each solution that you discussed
or looked at extra materials for hints, you must mention it in your solution.
This will not incur any penalty, but if noticed otherwise by the graders, it
might question your academic integrity, and there might be more severe
repercussions.
For most other incidents, the standard CIMS academic integrity
policy applies.
You should not
consult previous years' students, code, assignments, etc. You may help other
students and groups on specific technical issues, but you must acknowledge such
interactions.
Anything you use from other sources (other
students, web, etc.) must be acknowledged. Failure to do so will result in a zero
grade for the submitted work and, except in cases of obvious mistakes, a
University investigation.
Students are expected
to attend every meeting of the class. Students are also expected to participate
actively in course discussions. Participation will be taken into account in the
final grade. Details on how participation will be figured into the grade
can be found on the Brightspace page.
In this class, we will be using Desmos classroom activities. The
use of this software is for educational purposes only. This third-party
software is not an NYU-supported service with data privacy, FERPA, and security
protections in place (like your NYU Gmail, NYU Brightspace, etc.). I will
structure assignments so that no highly sensitive information is needed to use
the tool, but please note that we are subject to the terms of use set by the
platform's developer https://www.desmos.com/terms If you have any concerns about the platform,
please let me know as soon as possible.
The work you submit should be your own. Please consult the CAS academic integrity policy for more information. Penalties for violations of academic integrity may include failure of the course, suspension from the University, or even expulsion.
As a non-sectarian, inclusive institution, NYU policy permits members of any religious group to absent themselves from classes without penalty when required for compliance with their religious obligations. The policy and principles to be followed by students and faculty may be found in the University Calendar Policy on Religious Holidays.
Academic accommodations are available to any student with a chronic, psychological, visual, mobility, learning disability, deaf, or hard of hearing. Students should please register with the Moses Center for Students with Disabilities at 212-998-4980.
NYU's Henry and Lucy Moses Center for Students with Disabilities
726 Broadway, 2nd Floor
New York, NY 10003-6675
Telephone: 212-998-4980
Voice/TTY Fax: 212-995-4114
Web site: http://www.nyu.edu/csd