30516  THEORETICAL COMPUTER SCIENCE
Department of Decision Sciences
MAREK ELIAS
Suggested background knowledge
Mission & Content Summary
MISSION
CONTENT SUMMARY
 Divideandconquer algorithms
 Graph algorithms: connectivity
 Graph algorithms: shortest path
 Graph algorithms: minimum spanning tree
 Greedy algorithms
 Dynamic programming algorithms
 P, NP, NPcompleteness
 Decidability and undecidability
 Cryptography: definitions of security
 Crytpography: encryption and authentication
Intended Learning Outcomes (ILO)
KNOWLEDGE AND UNDERSTANDING
 Know a number of examples of divideandconquer algorithms and how to solve recursive equations
 Understand how to model problems as networks, and know what network problems admit efficient algorithms
 Know how to devise an "exchange argument" to prove the correctness of a greedy algorithms
 Know how to identify a useful subproblem structure in dynamic programming
 Understand the notion of NPcompleteness and its applications, and be familiar with a number of known NPcomplete problems
 Understand the proof of undecidability of the halting problem, and be a familiar with a number of knonw undecidable problems
 Understand precise definitions of security in encryption and authentication, and the shortcomings of simple encryption schemes such as the ECB mode of encryption
APPLYING KNOWLEDGE AND UNDERSTANDING
 Identify problems that admit divideandconquer algorithms, devise efficient recursive algorithms for such problems, analyze the running time of such algorithms
 Apply notions such as connectivity and shortest paths to network data, and how to use depthfirstsearch graph visit as a framework to develop new algorithms
 Recognize problems that can be optimally solved with greedy algorithms, and be able to write efficient code for such problems and to verify correctness with an "exchange argument"
 Recognize problems that can be optimally solved with a dynamic programming approach, and be able to write efficient code for such problems
 Recognize problems that are NPcomplete, and be able to devise simple NPcompleteness proofs
 Recognize problems that are undecidable, and be able to devise simple undecidability proofs
 Be able to apply definitions of security in encryption and authentication, and be able to spot potential problems in a proposed cryptographic protocols
Teaching methods
 Facetoface lectures
DETAILS
The details should be erased, the homeworks will be graded now
Assessment methods
Continuous assessment  Partial exams  General exam  


x  x  

x 
ATTENDING AND NOT ATTENDING STUDENTS
Assessment will be the same for attending and nonattending students.
Written exam (70% of the final grade) consists of openended questions,
some of which will test the student's understanding of the concepts
developed during the course (for example, the ability to reason about
graphs, to reason about the correctness of a given algorithm, or to analyze
the running time of a given
algorithm) and some of which will test the student's ability to apply such
concepts to new contexts, for example their ability to devise an algorithm
for a new problem, to prove the NPcompleteness of a new problem, or to
prove the undecidability of a new problem.
Students can take the first partial written exam in the middle of the
semester and complete the second partial exam at the end of the course. In
this case the weight is: 35% for the first partial exam and 35% for the
second partial exam.
Alternatively, students can take a final written exam that accounts for 70%
of the final grade.
Teaching materials
ATTENDING AND NOT ATTENDING STUDENTS
There is no required textbook. Recommended textbooks will be communicated to the students at the start of classes. Lecture notes will be provided for selected topics.