Instructor: Dimitris
Papamichail
Office: Forcina
Hall 458
Email: papamicd (at tcnj)
(most
emails are answered within 24 hours during business days)
Office
Hours: Tuesdays
and Fridays 5pm – 6:30pm,
and
by appointment.
Class
Time: Tuesdays/Fridays
2pm – 3:20pm
Class
Room: Forcina
Hall, room 409 (or 406)
Course Description
This course presents the
major principles of algorithm design and analysis, and applies those principles
to classical problems in computer science. Topics include algorithm complexity,
data structures, divide and conquer, searching and sorting, greedy algorithms, graph
search and traversal, network flow, bipartite matching, dynamic programming,
approximate string matching, partitioning, skip lists, and union-find.
Prerequisites: CSC 230 or
250, and CSC 270, both with a minimum grade of C.
Course
Units: 1
Course
Materials
Textbook – The
required textbook for this course is:
Other useful books in the field are:
Course Requirements
á
Readings
& Participation
á
Homework
assignments
á
Programming
assignments
á
Presentation
á
Midterm
exam
á
Final
exam
Course Purpose &
Learning Goals
The purpose of
this course is to provide students with an introduction to algorithms and data
structures. By the end of the course students will be able to:
1.
Understand
the distinction between constant factor improvements in performance and
improvements in asymptotic growth rates.
2.
Given
an algorithm, empirically or analytically determine its complexity.
3.
Given
a problem for which efficient algorithmic techniques are known, research and
apply those techniques.
4.
Given
a problem for which no efficient algorithmic techniques are known, apply major
principles of algorithm design to seek a suitable algorithmic solution.
Other outcomes addressed
by the course:
1.
An
ability to analyze a problem, and identify and define the computing
requirements appropriate to its solution
2.
An
ability to apply mathematical foundations, algorithmic principles, and computer
science theory in the modeling and design of computer-based systems in a way
that demonstrates comprehension of the tradeoffs involved in design choices.
In this class,
the deep learning outcomes associated with TCNJÕs 4th hour are
accomplished by algorithmic problem assignments involving analytical and
creative thinking, which require the students to devote additional research
time towards solving them, and the discussions that take place about these
assignments in and out of class.
Course Topics and
Schedule (subject to change)
Topics and Schedule are
listed below. Note that dates are tentative and deviations will be made as
needed.
Dates |
Topic |
Assignment |
1/24 |
Introduction |
|
1/27 |
Reasoning about
correctness, problem modeling |
|
1/31 |
Machine models, big-Oh
notation |
Homework Assignment 1 (due on 2/7) |
2/3 |
Growth rate and
dominance, logarithms and properties |
|
2/7 |
Elementary data
structures |
Homework Assignment 2 (due on 2/14) |
2/10 |
Dictionary data
structures |
|
2/14 |
Trees |
Programming Assignment 1
(due 2/24) |
2/17 |
Heapsort |
|
2/21 |
Priority queues |
|
2/24 |
Quicksort |
|
2/28 |
Linear sorting |
Homework Assignment 3 (due on 3/7) |
3/3 |
Binary search |
|
3/7 |
Divide and conquer |
Midterm preparation |
3/10 |
Midterm |
|
3/14 |
No class – Spring break |
Homework Assignment 4 (due on 3/24) |
3/17 |
||
3/21 |
Data structures for
graphs |
|
3/24 |
Programming Assignment 2
(due on 4/4) |
|
3/28 |
Breadth First Search
(BFS) |
|
3/31 |
||
4/4 |
Depth First Search (DFS) |
Homework Assignment 5 (due on 4/11) |
4/7 |
||
4/11 |
Minimum spanning trees |
Programming Assignment 3
(due 4/21) |
4/14 |
Shortest paths |
|
4/18 |
Bipartite matching |
|
4/21 |
Space/Time tradeoff |
Presentations (due on
4/28) |
4/25 |
Approximate string
matching |
|
4/28 |
Longest increasing
subsequence |
Homework Assignment 6 (due on 5/5) |
5/2 |
The partition problem |
|
5/5 |
Review |
|
Course Policies
á
Course
material will be posted on canvas.
Check often.
á
We
will utilize the Piazza platform (www.piazza.com) for questions and discussions. Piazza is
also accessible through canvas. Please make sure you register at the beginning
of the semester.
á
Homework
assignments will be turned in via canvas, and a hard copy will be
delivered in class. Failure to deliver a printed copy at the beginning of class
will result in a 10% grade penalty.
á
Multiple
page assignments have to be stapled together. Unstapled copies will receive a
5% penalty.
á
Assignments
missing crucial information such as names,
course number, assignment number, and date will
receive a 5% penalty.
á
Late work
deliverables are accepted with penalty: 20% per day.
á
Grades
can be disputed for one week following the return of graded work only.
á
Please
be on time and prepared for class, and silence all cell phones before class
starts.
Additional
Information:
The midterm and final exams
may include problems that are similar to ones encountered in the homework
assignments. Failing to solve these problems will indicate a lack of individual
effort in the homework assignments.
Grading
Grades
will be assigned as follows:
o
Class
participation: 10%
o
Homework:
30%
o
Programming
Assignments: 15%
o
Presentation:
5%
o
Midterm
exam: 15%
o
Final
exam: 25%
Letter
grades are assigned in relation to final score. Traditionally scores above 90%
receive ÔAÕ, scores from 75% – 90% receive ÔBÕ, scores from 60% to 75%
receive ÔCÕ, scores from 50% to 60% receive ÔDÕ, and scores below 50% receive
ÔFÕ, although ranges may vary.
Selected TCNJ Policies
TCNJÕs final
examination policy is available on the web: http://policies.tcnj.edu/policies/digest.php?docId=9136
Attendance
Students are
expected to be present, on time, and prepared to participate in each scheduled
class session as detailed in TCNJÕs attendance policy, available on the web at:
http://policies.tcnj.edu/policies/digest.php?docId=9134
Academic
Integrity Policy
The Academic
Integrity Policy of TCNJ, available on the web at: http://policies.tcnj.edu/policies/digest.php?docId=7642
Americans
with Disabilities Act (ADA) Policy
Any student who
has a documented disability and is in need of academic accommodations should
notify the professor of this course and contact the Office
of Differing Abilities Services (609-771-2571). Accommodations are individualized and in accordance
with Section 504 of the Rehabilitation Act of 1973 and the Americans with
Disabilities Act of 1992.
TCNJÕs
Americans with Disabilities Act (ADA) policy is available on the web:
http://policies.tcnj.edu/policies/digest.php?docId=8082