**DATA STRUCTURES AND ALGORITHMS**

**SE
2C03 (Winter 2018)**

*** * * This outline is constantly
updated. Students should consult this page regularly for all
information relevant to this course * * ***

**Instructor**

Dr. George Karakostas

ITB/218, ext 26132, Mac address: karakos

Office hours: Tue, Thu 4:00 - 6:00 PM

**Course Assistance**

Eric Lefort (leforte@mcmaster.ca),
office hours: Thur. 4:30-5:30 pm, Rm. ITB/115

Kelvin Lin (linkk4@mcmaster.ca),
office hours: Mon. 4:30 - 5:30 pm, Mills Library 1st floor (send
email)

Ahmed Khan (khana97@mcmaster.ca), office hours: Tue. 3:30 - 4:30 pm, Thode Library 1st floor (send email)

**Schedule**

Term II, 2017/18

Tu Th Fr, 2:30 - 3:20 PM, Rm TSH B105

**Tutorials**

Session 1: Mo 2:30 - 3:20
PM, Rm T13 107

Session 2: We 2:30 - 3:20 PM, Rm T13 107

Session 3: Th 3:30 - 4:20PM, Rm BSB 117

**Prerequisites**

**SFWR ENG 2DM3**

Course Objectives

In this course, we will study the
concepts behind the technology of algorithms and data
structures. The algorithmic solution of problems arises in any
Computer Science or Software Engineering (indeed, *any *engineering
or science) issue. Our goal will be: (i) To appreciate that
algorithms and data structures are a *technology *(just
as, say, electrical circuit design, or large software system
design); this will be done by introducing performance
measurement in order to measure algorithmic efficiency (in this
course we will limit ourselves to efficient usage of *time*,
and, sometimes, *space*). (ii) To recognize the details
and nuances of modelling basic problems such as sorting,
searching, graph exploration, etc. that will always show up in a
Computer Scientist's or Software Engineer's career, and take
advantage of these details in order to design better algorithmic
solutions; not all algorithms that solve a problem are good, and
no algorithm is good for all problems. (iii) To practice the art
of reducing a given problem or application to other problems for
which we already have good algorithms.

More specifically, students should know and understand:

- Worst case analysis of algorithms
- Basic searching algorithms (elementary sorts, quicksort, mergesort, heapsort)
- Basic sorting algorithms (binary search, search trees, hashing)
- Elementary data structures (stacks, queues, priority queues, search trees, heaps, hash tables, tries, graph representations)
- Graph algorithms (topological sort, breadth/depth-first-search, strongly connected components, minimum spanning trees, shortest paths)
- Basic string algorithms
- FSA's and Regular expressions

Students should be able to

- Analyze the running time of algorithms
- Identify the time/space trade-offs in designing data structures and algorithms
- Given a problem such as searching, sorting, graph and string problems, select from a range of possible algorithms, provide justification for that selection
- Understand implementation issues for the algorithms studied
- Reduce a given application to (or decompose it into) problems already studied

**Learning
objectives, indicators, and rubrics**** **

**Outline of Topics (roughly per
week)**

- Introduction (1.3)
- Analysis of algorithms - Union-Find (1.4, 1.5)
- Elementary sorts - Mergesort - Quicksort (2.1, 2.2, 2.3)
- Priority queues - Sorting applications (2.4, 2.5)
- Symbol tables - Binary search trees (3.1, 3.2)
- Balanced search trees - Hash tables - searching applications (3.3, 3.4, 3.5)
- Graph representation - BFS/DFS - Connected components - Topological sort (4.1, 4.2)
- Minimum Spanning Trees - Shortest paths (4.3, 4.4)
- String sorts - Tries (5.1, 5.2)
- Substring search - FSA's and regular expressions (5.3 except KMP, 5.4)

**Student Assessment (Grading)**

- Homework
assignments
**15%** - Midterm
exam
**40%****(Feb. 15, 2:30 - 5:00 pm, Rm. HH 305 (last name A-K), UH 213 (last name L-Z)****, Open book (only original hardcopy of the textbook, no notes), Chapters 1, 2, 3.1-3.3)** - Final
exam
**45%****(Open book (only original hardcopy of the textbook, no notes))**

**Policy on collaboration for
homework assignments: **Collaboration on the homework
assignments is highly encouraged, within reasonable limits.
Students are expected to discuss assignment problems with each
other, and to cooperate on solutions in groups of no more than 5
people. However, the final write-up should be done by individual
students (i.e. individual students should be able to explain
their solutions by themselves, if such an explanation is asked
for by the instructor) and the names of the collaborators should
appear on the paper. Cooperation and teamwork are necessary for
the success of any complex task (the design of algorithms being
one such task), and it is the instructor's hope that students
will come to appreciate them in a constructive way. Please see
the instructor if you need someone to collaborate with.

**Policy on delayed assignments: **Assignments
delivered between the lecture they were due and the following
lecture get 50% of total credit. After the following lecture, no
credit given.

**Policy on collaboration during
exams: ****ABSOLUTELY NO
COLLABORATION DURING EXAMS!!!**

**Resources**

**Required textbook:** **"Algorithms",
4th ed., by R. Sedgewick and K. Wayne. **

**Recommended textbook: "Elements of programming interviews",
by A. Aziz, T-H. Lee, A. Prakash**

**Algorithms visualization tools: **There
are many of those. One that can be particularly useful is the
tool developed by David Galles and you can find here.

**Other texts: **There are many
excellent (text)books that can be used for studying algorithms
and data structures. Here I give only a couple you may find
interesting, but don't feel discouraged from creating your own
"algorithmic library" and finding the books that fit your needs.
The subject of this course is rather challenging, and you will
benefit if you hear more than one person(=book) explain a
concept to you.

- "Introduction
to Algorithms", 3rd ed., by T.H. Cormen, C.E. Leiserson, R.L.
Rivest, and C. Stein.
**Note:**This book is a great reference book, although somewhat more advanced. - "Algorithms"
by S. Dasgupta, C. Papadimitriou, and U. Vazirani.
**Note:**This book is also an introductory text but in many topics it goes deeper, and also covers a somewhat different set of topics. - "Introduction
to the design and analysis of algorithms" by A. Levitin.
**Note:**This text is also introductory, but its organization of the material is different to ours: it develops design techniques and then it applies them to problems, i.e., it's "technique oriented"; we take the "problem oriented" approach, where we study algorithms for specific problems and then we try to distil general techniques. The two approaches are not totally independent, but you may find it interesting to see another aspect of teaching the same material. - "Algorithm
design" by J. Kleinberg and E. Tardos.
**Note:**A little more advanced text that is more oriented towards the design of algorithms and is as much concerned with the nitty-gritty of implementation. - ...(your favourite book goes here)
- Me (yes,
me, your instructor): If you find something interesting, or
think of a problem you don't see how to solve, or want to know
more about a topic, please make use of the office hours and
come talk to me; I may be able to give you a pointer or two.

**Academic Dishonesty**

**"Academic dishonesty consists of
misrepresentation by deception or by other
fraudulent means and can result in serious consequences, e.g.
the grade of
zero on an assignment, loss of credit with a notation on the
transcript
(notation reads: "Grade of F assigned for academic
dishonesty"), and/or
suspension or expulsion from the university.
It is your responsibility to understand what constitutes
academic
dishonesty. For information on the various kinds of
academic dishonesty
please refer to the Academic Integrity Policy, specifically
Appendix 3,
located at
http://www.mcmaster.ca/senate/academic/ac_integrity.htm
The following illustrates only three forms of academic
dishonesty:
1. Plagiarism, e.g. the submission of work
that is not one's own or for which other credit has been
obtained. (e.g. submitting a copy of someone else's
writeup for an assignment)
2. Improper collaboration in group work.
(e.g. collaboration between groups in an assignment)
3. Copying or using unauthorized aids in
tests and examinations."
**

**Faculty Notices**

**"The Faculty of Engineering is
concerned with ensuring an environment that is free of all
discrimination. If there is a problem, individuals are
reminded that they should contact the Department Chair, the
Sexual Harrassment Officer or the Human Rights Consultant, as
the problem occurs."**

**"The instructor and university reserve the right to modify
elements of the course during the term. The university may
change the dates and deadlines for any or all courses in
extreme circumstances. If either type of modification becomes
necessary, reasonable notice and communication with the
students will be given with explanation and the opportunity to
comment on changes. It is the responsibility of the student to
check their McMaster email and course websites weekly during
the term and to note any changes."
**

Assignments

All assignments are to be submitted to the instructor at the beginning of the lecture.

**Assignment 1 (Due beginning of
lecture Fri. 19/1): **The
questions are here.** **The solutions are here.

Assignment 2 (Due ** beginning of lecture Fri. 2/2):
**The questions are here.

Assignment 3 (Due beginning of lecture Tue. 13/2):

To read the assignment files, you'll need the Adobe Reader, which is here.

Slides

The lecture slides are a collection
of textbook figures and other material. You can find them at the
textbook site here.