# COL100 Introduction to Computer Science

## General Information

Co-Instructor: Subodh Sharma (email: svs at cse.iitd.ac.in)
Semester: II, 2019-2020
Timings: Mon/Thur 09:30-11:00
Class Venue: LH 108 (Group 31-40)
Lab Venue: LH 502-505

## Notice

1. All mails to the course instructor MUST have COL100 as the subject.

## Honour Code

• All students are expected to follow the highest ethical standards.
• Collaborations and discussions are encouraged. However, all students are required to write up all solutions entirely on their own. Any collaboration, or help taken, must be declared.
• Students are encouraged to refer to books, papers and internet resources. They may even consult other individuals. However, the source must be clearly cited if any part of the solution (or even an idea) is taken from such a source.
• Failure to declare any help taken will be interpreted as academic misconduct.

## Course Overview

Click here to see what the Courses of Study booklet has to say.

COL100: Introduction to Computer Science is intended for First Year B. Tech. students. The course COL100 addresses on the following issues:

1. Problem formulation in a precise and concise fashion and independent of language considerations.
2. The design of an algorithm from the problem specification – its correctness and analysis of its efficiency.
3. The intermediate steps in the design of a program from an algorithm through a process of step-wise refinement. Language dependent considerations may be used in this process, but not elsewhere.

The emphasis throughout the course is in the analysis required while designing correct and efficient algorithms. The course is intended to teach a student a systematic process of design - beginning with problem formulation from an informal specification, through convincing arguments to algorithms, the analysis of their correctness and efficiency, and finally arriving at programs through a process of step-wise refinement. A programming language bias is avoided and programs are developed in both imperative and functional styles.

The first part of the course introduces the basics of the functional and imperative models of computation, recursive and iterative processes, and the basics of programming using higher-order functions. The programming languages used for functional and imperative programming are Standard ML and Python, respectively.

The second part of the course introduces data-directed programming. It emphasizes on programming with records, lists, trees, arrays and developing abstract data types.

The third part of the course addresses the issues in design and analysis of simple algorithms. Examples are taken from Divide and conquer, Backtracking, Numerical algorithms, Randomized algorithms and Geometric algorithms.

## References

The primary references is going to be the Lecture Notes on Introduction to Computing developed by Prof. Subhashis Banerjee and Prof. S. Arun-Kumar.

Other References

1. Structure and Interpretation of Computer Programs by Harold Abelson and Gerald Sussman with Julie Sussman, MIT Press, 1985.

2. How to solve it by Computer by R. J. Dromey, Prentice-Hall India EEE Series.

3. SML Tutorial, another SML Tutorial

4. Python resources:

Minor I - 22.5%; Minor II - 22.5%; Major - 30%; Programming assignments - 25%;

### The riot act:

As per the Institute regulations, an A grade will be awarded only over 80% and no student with less than 30% will be given a passing grade.

An I grade will be awarded only in the case of an illness during the major exam. A make-up exam will be scheduled at the earliest, and the I grade will be converted as soon as possible. However, please do your best to ensure that you donot break a leg or otherwise fall ill during examinations. Repeat examinations are harder by tradition.

### Other Policies:

• Attendance: The Institute requires a mandatory 75% attendance for all students, which includes time lost due to illness. However this course will require 100% attendance. Please inform the instructor if for any reason you cannot attend a class. Be warned that it will be difficult to make up if you miss classes.

• Illness: In sickness or ill-health, a Medical Certificate from the Institute Sick Bay, or a doctor from an Institute-recognised hospital is necessary, especially if you request for a make-up test. Only in the case of serious illnesses will I consider giving an extension on assignments.

• Make-up Tests: Make-up tests (minor or major exams only) will be given only when the student furnishes a valid documentation of illness for a period including the day of the exam.

• Late policy: Normally, I will not consider any assignments turned in late. In cases of illness I may consider giving an extension, provided the student informs me as soon as possible.

## Class notes and Programs developed in the class

Week Monday Thursday Supplementary Reading Programs in class
1 Dec 30
L1:Introduction
Jan 2
L2:Functions,Relations and PMI
Read Chapter 1,2 of the Lecture Notes and solve Chapter 2 exercise questions 1,2,6,9
2 Jan 6
More on PMI, Iterative function definitions via tail recursion
Jan 9
More examples on Tail recursion + SML Tutorial
Read section 3.1 to 3.5 and 3.9 of the Lecture Notes
3 Jan 11
Discussion on Assignment 1 questions, Scoping rules, Complexity Analysis
Jan 13
More on Complexity analysis: Big O, Recurrence Relations, Time and Space Complexity
Read section 3.8 and 3.6 of the Lecture Notes IntSqRoot.sml, Scoping.sml
4 Jan 20
Iterative Fibonacci, Pascal Triangle, More on invariants and recurrence relations
Jan 24
Recursive formulation of counting change problem, McCarthy 91 function
5 Jan 27
technical Completeness, Recursive formulation of Towers of Hanoi
Jan 30
More problems on recursion
Solve problems on pg. 51 of Lecture Notes
6 Feb 3 Feb 5
Minor1 exam and solutions
7 Feb 10
Higher Order Functions, Polymorphic Functions
Feb 13
More on Higher Order Functions, Polymorphic Functions
Read Chapter 5 sections 5.1 and 5.2 accumulator.sml, root.sml
8 Feb 17
Data Abstraction: Rationals and Lists
Feb 20
More on Lists: length, append, reversal
Read sections 6.1 and 6.2 and 7.1 rationaltype.sml
9 Feb 24
Sorting using Lists: Insertion sort, Mergesort
Feb 27
Mergesort and Quicksort on Lists