Queen's School of Computing CISC/CMPE-365* - Fall 2016 Title
CISC-365*

Algorithms I


Fall 2017


XKCD Algorithms

Internal LinksAnnouncements

Personnel

Course Information

Schedule

Course Plan and Record

Practice Problems

Recommended Readings

Sample Tests

Academic Integrity in CISC 365


External_Links
External Links
Queen's School of Computing
Computing Students' Association
Class Photo Gallery
Learning - Your First Job (Paper by Dr. R. Leamnson) - ESSENTIAL READING
Academic Integrity






Announcements

Announcements
Date Subject Text














Return to menu



Personnel

Personnel
Instructor
Dr. Robin W. Dawes
RWD
Goodwin 537 
dawes AT cs DOT queensu DOT ca
http://sites.cs.queensu.ca/dawes/
533-6061 (but e-mail is a much better idea)
Office Hours: TBA

TAs
Name
Email 
Office Hours
Picture









































Return to menu



Course Information

Course_Information
Calendar Description
Principles of design, analysis and implementation of efficient algorithms. Case studies from a variety of areas illustrate divide and conquer methods, the greedy approach, branch and bound algorithms and dynamic programming.
Text
Cormen/Leiserson/Rivest/Stein, Introduction to Algorithms (3rd Edition)
Syllabus
Complexity of algorithms and Complexity of problems: Reducibility, P, NP, NP-Completeness, etc.
Divide and Conquer Paradigm: Quicksort, Median, Closest Pair of Points, etc.
Principle of Optimality
Dynamic Programming Paradigm: Longest Common Subsequence, Chained Matrix Multiplication, etc.
Greedy Paradigm: Huffman Coding, Activity Selection, Minimum Weight Spanning Trees, etc.
Branch-and-Bound Paradigm: 15-Puzzle, Travelling Salesperson Problem, etc.
Class Choice (three or more topics will be proposed, the class will choose one by vote)
Marking Scheme
There will be five 50-minute tests.  The lowest of the five marks will count for 12%, and the other four will each count for 22%





Return to menu



Schedule

Schedule_Table
Class Schedule



Tuesday 2:30 - 3:20
Wednesday 4:30 - 5:20
Friday 3:30 - 4:20







Test Schedule


Date
Location
Material
Solutions
Test 1
Friday October 6
TBA


Test 2
Friday October 20
TBA


Test 3
Friday November 3
TBA


Test 4
Friday November 17
TBA


Test 5
Friday December 1
TBA





Return to menu



Course Plan and Record

Record Table

Week 1 Tuesday, September 12
Plan: Intro and Review
PPT Slides
Dijkstra's Algorithm 
Wednesday, September 13
Plan: NP-Completeness
Problems - some solvable, some not

Friday, September 15
Plan: NP-Completeness
Magical Computers and Classes of Problems
Week 2 Tuesday, September 19
Plan: NP-Completeness

Wednesday, September 20
Plan:  NP-Completeness

Friday, September 22
Plan: NP-Completeness

Week 3 Tuesday, September 26
Plan: CNF-SAT to k-Clique

Wednesday, September 27
Plan: Subset Sum

Friday, September 28
Plan: Dividing and Conquering


Week 4 Tuesday, October 3
Plan: Closest Pair of Points

Wednesday, October 4
Plan: Road Trip!

Friday, October 6
TEST 1


Week 5 Tuesday, October 10
Plan: Greedy Algorithms

Wednesday, October 11
Plan: Greedy Activity Selection

Friday, October 13
Plan: Huffman Coding


Week 6 Tuesday, October 17
Plan: Knapsacks and Trees

Wednesday, October 18
Plan: Nine Walkers
Friday, October 20
TEST 2

Week 7 Tuesday, October 24
Plan: Dynamic Programming
Wednesday, October 25
Plan: Dynamic Programming
Friday, October 27
Plan: Dynamic Programming

Week 8 Tuesday, October 31
Plan: The End of Dynamic Programming
Wednesday, November 1
Plan: Search for Tut's Tomb

Friday, November 3
TEST 3
Week 9 Tuesday, November 7
Plan: Branch and Bound

Wednesday, November 8
Plan: More Branching

Friday, November 10
Plan: More Bounding

Week 10 Tuesday, November 14
Plan: End of Branch and Bound
Wednesday, November 15
Plan: 
Friday, November 17
TEST 4

Week 11 Tuesday, November 21
Plan: Class Choice
Wednesday, November 22
Plan: Class Choice
Friday, November 24
Plan:


Week 12 Tuesday, November 28
Plan: Class Choice
 
Wednesday, November 29
Plan:  Mystery
Friday, December 1
TEST 5




Return to menu



Practice Problems

Practice Problems Table
Source
Page Exercise Set
Exercises
Text 11 1.1 1, 2, 4, 5

29 2.2
1, 2, 4

37 2.3
3, 4, 5, 6, 7

39 Chapter 2 Problems
2-3 a, b
2-4 a, b, c, d

52 3.1 1, 2, 3

60 3.2
1, 8

61 Chapter 3 Problems
3-2
3-4 a, b, d, e

107 Chapter 4 Problems
4-1 a, b, g
4-2

1101 Chapter 34 Problems
34-1 d
34-2 a
34-3 a

369 15.1
2, 3

389 15.3 5

396 15.4
1, 5, 6 (hard)

404 Chapter 15 Problems
1, 2, 3, 4

421 16.1
1, 2, 3, 4

427 16.2
3, 7

436 16.3
2, 6

446 Chapter 16 Problems
1
course website

B&B Practice Problems


1111 35.1 1, 3 (hard)

1116 35.2 1, 5

1127 35.4
1



























Return to menu



Recommended Readings

Readings
Source Chapter
Details
Target Date




Text
1
should be familiar ideas
Text
2
scan this

Text
3
the essential ideas here are the "big O", "omega" and "theta" definitions and applications

Text
4
- review the substitution method and the recursion-tree method (not covered in class)
- you are not required to learn the master method, but it is a very powerful tool - study it if you have time

Electronic Enterprises Laboratory
http://lcm.csa.iisc.ernet.in/dsa/node216.html
a brief but clear introduction to NP-Completeness, very similar to the approach we will take in class

Wikipedia

http://en.wikipedia.org/wiki/List_of_NP-complete_problems
Just as it says, this is a big list of NP-complete problems

Wikipedia

http://en.wikipedia.org/wiki/P_%3D_NP_problem
A reasonably good summary of the problem classes P and NP and the relationship between them.  Much easier to read than our text on this subject.

mathreference.com

http://mathreference.com/lan-cx-np,intro.html
This collection of pages takes the same approach to the topic as we did (concentrating on problems and algorithms, rather than on formal languages) but it strays into error quite quickly.  In fact, it contains some oversimplifications and some blatant errors that you should be able to spot.  Good hunting!

Text
15
Intro, 15.1, 15.3, 15.4

Text
16
Intro, 16.1, 16.2, 16.3

The internets

Branch and Bound sources:
    http://www.imada.sdu.dk/Courses/DM85/TSPtext.pdf
    http://www.lpds.sztaki.hu/pgrade/nagy_miklos/index.html
    http://www.cs.berkeley.edu/~demmel/cs267-1995/assignment5.html
    CMSC 132 Lecture







Here are some of the sources I used when preparing the lectures on Genetic Algorithms:

https://svn-d1.mpi-inf.mpg.de/AG1/MultiCoreLab/papers/ebook-fuzzy-mitchell-99.pdf

We covered some of Chapter 1 of Mitchell's book.  There are some practice questions at the end of the chapter, but many relate to material we did not cover.

http://www.iitg.ernet.in/rkbc/CE602/CE602/Genetic%20Algorithms.pdf

The pdf listed above contains many examples but they are not very well explained.

http://www.slideshare.net/paskorn/simulated-binary-crossover-presentation

This set of slides gives a fairly good explanation of simulated binary cross-over.  The formulas are slightly different from the ones we used in class but the result is identical.
































Return to menu



Sample Tests

365 Sample Tests
Test 1

Test 2

Test 3

Test 4

Test 5



Return to menu



Academic Integrity in CISC 365

Academic integrity is constituted by the five core fundamental values of honesty, trust, fairness, respect and responsibility (see www.academicintegrity.org). These values are central to the building, nurturing and sustaining of an academic community in which all members of the community will thrive. Adherence to the values expressed through academic integrity forms a foundation for the "freedom of inquiry and exchange of ideas" essential to the intellectual life of the University (see the Senate Report on Principles and Priorities).

Students are responsible for familiarizing themselves with the regulations concerning academic integrity and for ensuring that their assignments conform to the principles of academic integrity. Information on academic integrity is available in the Arts and Science Calendar (see Academic Regulation 1 on the Arts and Science website) and from the instructor of this course.

Departures from academic integrity include plagiarism, use of unauthorized materials, facilitation, forgery and falsification, and are antithetical to the development of an academic community at Queen's. Given the seriousness of these matters, actions which contravene the regulation on academic integrity carry sanctions that can range from a warning or the loss of grades on an assignment to the failure of a course to a requirement to withdraw from the university.

The preceding text on academic integrity is based on a document written by Prof. Margaret Lamb and is used here with her permission.



Return to menu