Lecture Notes for CS120 An Introduction to Computing

It is copyrighted bySubhashis Banerjee S. Arun-Kumar

Department of Computer Science and Engineering
            Indian Institute of Technology


DOWNLOAD LINK    MIRROR


CONTENTS

I Models of computation

1 Introduction

2 Mathematical preliminaries
2.0.1 Sets
2.0.2 Relations and Functions
2.0.3 Principle of Mathematical Induction

3 A functional model of computation
3.1 The primitive expressions
3.2 Substitution of functions
3.2.1 Substitution using let
3.3 De nition of functions using conditionals
3.4 Functions as inductively de ned computational processes
3.5 Recursive processes
3.6 Analysis of correctness and e ciency
3.6.1 Correctness
3.6.2 E ciency
3.6.3 E ciency, Why and How?
3.6.4 In the long run: Asymptotic analysis and Orders of growth
3.7 More examples of recursive algorithms
3.8 Scope rules
3.9 Tail-recursion and iterative processes
3.9.1 Correctness of an iterative process
3.10 More examples of iterative processes

4 The Imperative model of computation
4.1 The primitives for the imperative model
4.1.1 Variables and the assignment instruction
4.1.2 Assertions
4.1.3 The if then else instruction
4.1.4 The while do instruction
4.1.5 Functions and procedures in the imperative model

5 Step-wise re nement and Procedural Abstraction 71
5.1 Step-wise re nement
5.1.1 Executable speci cations and rapid-prototyping
5.1.2 Examples of step-wise re nement
5.2 Procedural abstraction using higher-order functions
5.2.1 Functions as input parameters
5.2.2 Polymorphic functions
5.2.3 Constructing functions using lambda ( )
5.2.4 Functions as returned values


II Data-directed programming 107

6 Abstract Data Types 109
6.1 Building the Rational data-type (pairs)
6.2 Rational data-type in ML
6.2.1 signature, datatype and module
6.3 Rational data-type in Java
6.3.1 Interfaces, Classes and Objects: Basics of Object Oriented Programming .

7 Programming with Lists
7.1 Lists
7.2 The Alpha- LIST data-type in ML
7.3 The Alpha-LIST data-type in Java
7.3.1 Sharing of lists and garbage collection
7.3.2 List programming in Java

CS125 Introduction to Computer Science Lecture Notes ebook

That book is copyrighted by Jason Zych. 

Part 1 : Programming Basics 1

Lecture 1 : Computer Science and Software Design
Lecture 2 : Architecture and Program Development
Lecture 3 : Types, Variables, and Expressions
Lecture 4 : Type Checking, Input/Output, and Programming Style
Lecture 5 : Boolean Expressions, Simple Conditionals, and Statements
Lecture 6 : Compound Statements, Scope, and Advanced Conditionals
Lecture 7 : Loops
Lecture 8 : One-Dimensional Arrays
Lecture 9 : Multi-Dimensional Arrays
Lecture 10 : Processing Data Collections


Part 2 : Programming Methodologies

Lecture 11 : Procedural Composition and Abstraction
Lecture 12 : Method Syntax
Lecture 13 : Reference Variables and Objects
Lecture 14 : Objects and Methods
Lecture 15 : Data Composition and Abstraction: Classes and Instance Variables
Lecture 16 : Classes, Reference Variables, and null
Lecture 17 : Instance Methods
Lecture 18 : static versus non-static, and Constructors
Lecture 19 : Access Permissions and Encapsulation
Lecture 20 : Copying and Mutability


Part 3 : Algorithm Design and Recursion

Lecture 21 : Introduction to Algorithm Design and Recursion
Lecture 22 : Subproblems
Lecture 23 : Picture Recursion
Lecture 24 : Recursive Counting
Lecture 25 : Subarrays – Recursion on Data Collections
Lecture 26 : Searching
Lecture 27 : Sorting
Lecture 28 : Tail Recursion and Loop Conversion
Lecture 29 : Accumulator Recursion
Lecture 30 : More Accumulator Recursion


Part 4 : Algorithm Analysis

Lectures 31 and 32 : Introduction to Algorithm Analysis
Lecture 33 : Selection Sort Analysis
Lecture 34 : Insertion Sort Analysis
Lecture 35 : Exponentiation and Searching
Lectures 36 and 37 : Mergesort
Lectures 38 and 39 : Quicksort
Lecture 40 : Advanced Sorting Analysis

PDF FILE