Department Of Computer Science and Engineering

Kathmandu University
Dhulikhel, Kavre

Subject: ​Graph Theory​ Course: COMP – 323

Level: [Link]/3​rd​ Year/2​nd​ Semester Credit Hours: 3

Course Description

1. Fundamental Concepts
● Definitions and Examples
● Paths
● Vertex
● Isomorphism
● Subgraphs
● Types of Graphs
● Some applications

2. Trees
● Basic Properties
● Spanning Trees
● Optimization
● Counting trees
● Digraphs

3. Planar Graphs
● Definitions and examples
● Euler’s Formula
● Characterization
● Parameters

4. Graph Coloring
● Definitions
● Vertex coloring
● Bounds
● The four color problem
● Chromatic graphs
 5. Matching
● Definitions
● Maximum matching
● Hall’s matching conditions
● Perfect matching

6. Switching Theory
● Definitions
● Boolean Algebra
● Analysis of Contact Network
● Normal Form
● Transmission Matrix, Primitive Connection Matrix and relation between them

7. Activity Networks
● Definitions
● Analysis of Activity Network
● Earliest Event Time
● Latest Event Time
● Total & Free Slacks
● Critical Path Method

Reference Books:
1. SM Maskey – First Course in Graph Theory, 2nd Edition, Ratna Pustak Bhandar, 2002
2. Frank Harry – Graph Theory, Narosa Publishing House, 2001.
 Kathmandu University
Course of study
Course Title: Advanced Calculus Level: Undergraduate
Course Code: MATH - 201 Credit: 3
—————————————————————————————————————————–

Group(s): C.M./A.P. (II Year - I Semester)

Pre-requisite: Math - 101

Course Description: The course attempts to provide mainly calculus of several variables
with emphasis on the conceptual and problems solving skills on the topics of advanced calculus -
Coordinates in space, Multiple integrals, Line integrals, Stieltjes integral, Partial differentiations
and their applications and The Fourier series.

Objectives:

Upon the completion of this course, students will be able to

1. develop conceptual ideas on the topics.

2. develop problem solving skills.

Course Contents

Unit 1: Coordinates in Spaces [3 hours]

1.1 Cartesian Coordinates

1.2 Cylindrical Coordinates

1.3 Spherical Coordinates

1.4 Their Inter-relations

Unit 2: Multiple Integrals [8 hours]

2.1 Introduction - Review of Riemann integral, Some definitions, Rectangular and non-rectangular
regions in a plane, Limit definition of Double integrals, Existence of double integral the-
orem (statement only), Double integral of some simple functions using limit definition.

2.2 Properties of double integrals, Iterated integrals, Statement of The Fundamental theorem
(both rectangular and non-rectangular regions - The Fubini’s theorems), Evaluation of
double integrals using The Fundamental Theorem.

2.3 Reversing order of integration, Substitutions in multiple integrals Theorem (statement

only), Double integrals in polar coordinates (statment only), Evaluation of double integrals
in polar form.
Last updated : March 17, 2019

1
 2.4 Applications of double integrals - plane region area, average value, mass, First moments
and center of mass.

2.5 Triple Integrals - Limit definition, Existence of Triple integral theorem (statement only),
Properties of Triple integrals, The Fundamental theorem of Triple integral (statement
only), Evaluation of Triple integrals.

2.6 Triple integrals in other Coordinates system - Cylindrical and Spherical Coordinates.

2.7 Applications of Triple integrals - Volume, Average value, Mass, First moments and center
of mass.

Unit 3: Line Integrals [8 hours]

3.1 Introduction - Vector field, Divergence and Curl, Definition of line integral, Evaluation
for smooth curve, Properties of line integrals.

3.2 Applications of line integrals - mass, moments and center of mass.

3.3 Work, Different ways to write work, Evaluation of work, Flux integral and Circulation,
Flux across a plane curve.

3.4 Conservative vector field and potential function, Test for conservative vector field, Path
independence, Fundamental Theorem of line integral (proof), Evaluation of potential func-
tion.

3.5 Green’s theorem in a plane in Tangential form (proof standard region), Normal form
of Green’s theorem (statement only), Green’s theorem for multiply connected region,
Verification problems.

3.6 Applications of Green’s theorem - work done, area as a line integral, evaluation of line
integral in the plane, circulation and outward flux.

Unit 4: Partial differentiation [10 hours]

4.1 Introduction - partial derivatives, higher order derivatives.

4.2 Functions of one variable - Limits and continuity, Derivatives, Rolle’s theorem (proof),
Law of the mean (proof).

4.3 Functions of several variables - Limits and continuity, Derivatives, A basic mean value
theorem (proof), Composite functions Theorem (statement only).

4.4 Differentiable functions - Notion of differentiability for functions of one variable, Differ-
entiability in Rn , Related theorems (proof).

4.5 Homogeneous functions - Euler’s theorem (proof), Converse of Euler theorem (proof) in
R2 and R3 .

4.6 Mixed derivatives - Second order mixed derivatives and its theorem (statement only),
Related problems.

4.7 Implicit functions - Differentiation of implicit functions theorems (proof), Two equations
in two unknowns theorem (proof)

4.8 Jacobian - Change of variables, Jacobian theorem for inverse of a transformation (proof),
dependent and independent variables.

2
 4.9 Directional derivatives - definition of direction and directional derivatives, Directional
derivative theorem (proof), Gradient, Directional derivative and gradient theorem (proof)

Unit 5: Applications of Partial differentiation [6 hours]

5.1 Maxima and minima for one variable - Necessary conditions for absolute maxima/minima
(statement only), Sufficient conditions for relative maxima/minima (proof), point of in-
flection, derivative conditions for point of inflection (proof).

5.2 Maxima/minima for two/three variables - Sufficient conditions for relative maxima/minima
(statement only), Sufficient conditions for saddle point for functions of two variables (state-
ment only), Related problems.

Unit 6: Stieltjes Integrals [6 hours]

6.1 Review of Riemann integrals.

6.2 Definition of Stieltjes integral as a limit of sum, Existence of the integral theorem (state-
ment only), Evaluation of Stieltjes integrals as a limit of sum, Properties of definite inte-
grals.

6.3 Stieltjes integrals Theorem as a Riemann integral (statement only), Sums, Bounded varia-
tion, Bounded variation Theorem for Stieltjes integral (statement only), Related problems.

6.4 Integration by parts Theorem (proof), Related problems.

Unit 7: Fourier series and Beta and Gamma functions [4 hours]

7.1 Fourier series - Introduction; Fourier series of f (x), −π ≤ x ≤ π; Sine and Cosine Fourier
series; Fourier series of f (x) for an arbitrary period; Applications.

7.2 Beta and Gamma function - Introduction; Properties of Beta and Gamma functions;
Relations between Beta and Gamma functions; Transformation of Gamma function; Ap-
plications.

Text Books
1. David V Wider, Advanced Calculus, 2nd Edition, PHI.

2. Geroge B Thomas, Maurice D Weir & Joel R Hass, Thomas’ Calculus, Pearson.

3
 Department Of Computer Science and Engineering
Kathmandu University
Dhulikhel, Kavre

Subject: Statistics and Probability Course: MATH – 208

Level: BE/[Link]/1​st​ Year/1​st​ Semester Credit Hours: 3

Objective: ​The objective of the course is to provide students with a clear understanding of the
basic statistical concepts and tools and to enable them to use these tools as Necessary Avenue for
engineering professions and scientific knowledge.

1. Introduction to Statistics and Data Description (8)

● Graphical Presentation of Data
i. Dot Plots and Scatter Plots
ii. The frequency Distribution and Histogram
iii. The Stem-and-leaf Plot
iv. The Box Plot
v. The Pareto Chart
● Numerical Description of Data
i. Measures of Central Tendency: Mean, Median, Mode, Mean of combined
groups, Comparison of mean, median and mode.
ii. Measures of Dispersion: Range, Quartile deviation, Standard deviation &
Variance, Coefficient of Variation, Skewness and Kurtosis

2. Probability (6)
● Introduction
● A Review of Sets
● Random experiment, Sample space and Events (simple and composites), Mutually
exclusive and Collectively exhaustive events, Independent events
● Probabilities definition and Assignment
● Finite Sample Space and Enumeration
● Conditional probability
● Partitions, Total probability, and Bayes' theorem and its applications
3. One Dimensional Random Variables (2)
● Introduction
● The Distribution Function
● Discrete and Continuous Random variable
● Some Characteristics of Distributions (mean, variance)

4. Functions of One Random Variable and Mathematical Expectation (3)

● Introduction
● Equivalent Events
● Function of Discrete and Continuous Random variable
● Mathematical Expectation.

5. Some Important Discrete Distributions (4)

● Introduction
● Bernoulli Trials and the Bernoulli Distribution
● The Binomial Distribution
i. Mean and variance of Binomial Distribution
ii. The cumulative Binomial Distribution
iii. An application of Binomial Distribution
● The Poisson Distribution
i. Mean and variance of Poisson Distribution
ii. The Poisson Approximation to Binomial Distribution

6. The Normal Distribution (4)

● Introduction
● Properties of the Normal Distribution
● The Mean and Variance of the Normal Distribution
● The Normal Cumulative Distribution
● The Standard Normal Distribution
● Problem-Solving Procedure
● The Central Limit Theorem
● The Normal Approximation to Binomial Distribution

7. Random Samples and Sampling Distributions (3)

● Population and sample, Census and sampling, Estimate and estimator, Parameter
and statistic
● Random Samples
● Statistics and Sampling Distributions
● The Chi-Square Distribution
 ● The t-Distribution
● The F-Distribution

8. Estimation (4)
● Point Estimation, Interval estimation
● Properties of Estimators
● Single-Sample Confidence Interval Estimation (mean and variance)
● Two-Sample Confidence Interval Estimation (mean and variance)
9. Tests of Hypotheses (6)
● Introduction
● Tests of Hypotheses on a Single-Sample (mean and variance)
● Tests of Hypotheses on two Samples (mean and variance)

10. Simple Linear Regression and Correlation (4)

● Simple Linear Regression and interpretation
● Correlation and interpretation
● Coefficient of determination

11. Statistical Quality Control (4)

● Introduction, Statistical Process Control
● Control Charts for Measurements
● Control Charts for Individual Measurements
● Control Charts for Attributes

Textbook:
1. Probability and Statistics in Engineering, 4th Edition, by William W. Hines, Douglas C.
Montgomery, David M. Goldsman, and Connie M. Borror, John Wiley and Sons, Inc,
2003.

Reference Books:
1. Miller & Fruend’s Probability and Statistics for Engineers by Richard A Johnson
2. Statistics Concepts and Application by Nabendu Pal and Sahadeb Sarkar, Prentice Hall of
India Private Limited, 2005
3. Probability and Statistics by Purna Chandra Biswal, Prentice Hall of India Private
Limited, 2005
4. Modern Elementary Statistics by John E. Freund, 6th edition, Prentice Hall Int.
5. Statistics for Management by R. I. Levin and D. S. Rubin, 6th edition
 Kathmandu University
Course of study
Course Title: Analysis I

Course Code: MATH- 213 Level:

Undergraduate
Credit: 3

Group(): CM (I Year - II
Semester)

Course Description: This course includes the

real number system,
series, limits, continuity, and Riemann
real
sequences and
differentiability
Integrability of functions
their associated propertics. along with

Objectives:

Upon the completion of this

course, students will be able to
1. know the classical of real number system.
properties

2. develop basic ideas of

sequence and series, their convergence and limits.
3. understand the relation between the algebraic concepts of limits,
bility and RiemannIntegrability with their
continuity, differentia
geometrical meanings
4. be able to the
justify
theorems/propositions with appropriate examples and
amples. counterex

Course Contents
Unit 1: The real number system R [12 hours]
1.1 Preliminaries

1.1.1 Sets and functions

1.1.2 Axioms on R
1.1.3 Absolute value of a real number
1.2 Boundedness in R and supremum and ínfimum

1.3 The Completeness in R and associated properties

14 Interior, adherent and limit points on R; Open and closcd sets in R

Unit 2: Sequences and Series |8

hours
2.1 Sequence of real numbers and related properties

2.2
The Cauchy sequence and its
convergence criterion

2.3 Series
Infinite

date: March 17,

Revised 2019
 2.3.1 Necessary condition tor
convergence
2.3.2 Various tests ot convergence and
divergence

Unit 3: Limits of functions (4 hours)

3.1 Concept on limits; indeterminate forms

3.2 Theorems on limits

3.3 One-sided limits

Unit 4: Continuous functions [8 hours]

4.1 Continuous and properties
fhunctions relnted (together with boundedness and intermedlate
value theorems with proofs).

4.2 Combinations of continuous functions

4.3 Continuous functions on intervals

4.4 Uniform continuity of functions

Unit 5: Differentiat ions [8

hours
5.1 Deriveatives of functions and their properties
5.2 L'Hopital rules
(with proofs)

5.3 Taylor's Theoremn

Unit 6: Riemann Integration 15 hours

6.1 Partitions, Riemann sums and Riemann integrals
6.2 Existence and uniqueness theorem on Riemannintegral
6.3 Darboux sums and Darboux integrals

Text Books
1. Ravi P. Agarwal, Cristina Flaut and Donal O'Regan, An Introduction to Real Analysis,
Chapman and Hall/CRC, 2018.
2. R. G. Bartle and D. R. Sherbert, Introduction to Real Analysis, Wiley India Pvt. Ltd,
New Delhi, India.

Reference Books

1. and Nisha Rani, Fundamental of Real Analysis, Vikas Publishing House Pvt.
[Link]
Ltd, India.

2. S.C. Malik, Principles of Real Analysis, New Age International PVT, New Delhi.

3.
G. Das and [Link], Fundamentals of Mathematical Analysis, Tata McGraw Hill,

New Delhi.

4.
Shanti Narayanand M.
D. Raisinghania, Elements of Real Aralysis, s Chand & Company
Pvt. Ldt., New Delhi.
 Kathmandu University
Course of Study
Course Title : Computational Statistics Level : Undergraduate
Course Code : 403 Credit : 3

Group : CM (IV Year – I Semester)

Pre-requisite : MATH 208

Course Description :

The course will provide basis theory of random numbers, simulation- modeling techniques, bootstrapping,
some advanced statistical tests and regression analysis as well as time series. All the theory involved will
be applied practically using computer software.

Technology:

The course will be divided into theoretical and practical parts with proportions of 50% for theory and
50% for practical. For practical part 'R' programming language will be used to implement theoretical
concepts in real applied form.

Lecture Hours : 45

Evaluation Scheme:

a. In-semester evaluation – 50 marks

 Assignments – 5 marks, Internal tests – 20 marks, Lab-works – 25 marks
b. End-semester evaluation – 50 marks
 10 marks for objective [10Q x 0.5 = 5 marks for 'fill-in-the-blank' question and 10 Q x 0.5 = 5
mark for 'multiple-choice' question]
 40 marks for subjective [2 Q x 8 = 16 marks for long-answer questions and 8 Q x 3 = 24 for
short-answer questions]

Course Contents

Unit 1 : Introduction to R [6 hours]

1.1 Data manipulation
1.2 Data visualization
1.3 Generation of probability distributions

Unit 2 : Random number generation [6 hours]

2.1 Introduction, true random number generation (tRNG), pseudo-random number generation
(pRNG)
 2.2 Linear congruential method, Inverse transformation method
2.3 Tests for randomness

Unit 3: Simulation and modeling [10 hours]

3.1 Introduction to simulation and Monte Carlo simulation

3.1.1 Monte Carlo Integration
3.1.2 Variance reduction technique

3.2 Markov chains

3.2.1 Stochastic process
3.2.2 Discrete time and continuous time Markov Chain
3.2.3 Homogeneous MC
3.2.4 Steady-state distribution
Unit 4 : Bootstrapping [ 4 hours]

4.1 Introduction
4.2 Advantages
4.3 Features
4.4 Applications

Unit 5 : Data Analysis [10 hours]

5.1 Analysis of Variance (ANOVA)

5.2 Non-parametric tests
5.3 Curvilinear regression
5.4 Multiple regression
5.5 Logistic regression
5.6 Multiple and partial correlation

Unit 6 : Time series analysis [9 hours]

6.1 Data smoothing and forecasting

6.2 Autocovariance and autocorrelation function (ACVF and ACF)
6.3 Auto-regressive (AR) model
6.4 Moving Average (MA) model

Textbooks/ References-
 Computational Statistics, Givens and Hoeting, Wiley Series in Prob. and Statistics, 2005.
 Introduction to Time Series Analysis and Forecasting, Wiley Series- Douglas C. Montgomery,
Cheryl L. Jennings, Murat Kulahci
 Discrete Event System Simulation, Prentice Hall – Jerry Banks, John S. Carson, Barry L. Nelson,
David M. Nicol
 Statistics for Engineers and Scientists, McGraw Hill- 2008, William Navidi
 Kathmandu University
Course of study
Course Title: Mathematical Modeling Level: Undergraduate
Course Code: MATH - 404 Credit: 3
——————————————————————————————————————————

Group: CM (IV Year - II Semester)

Prerequisite: Math 101/MATH-217

Course Description:
Mathematical modeling is the description and analysis of real world problem mathematically,
and is rich with many interesting aspects. Mathematical models are use
d in various aspects of real life including natural sciences and engineering.

The course attempts to provide teaching with orientation in mathematical modeling concerning
the real world problems. The course includes modeling philosophy, discrete and differential
equations models, model fitting, experimental modeling and optimization models.

Course Objectives:
Broadly, the following are the objectives of this course

ˆ Understanding the modeling process.

ˆ Apply problem solving strategies confidently to real behavior problems.

Technology:
Appropriate Computer Algebra Systems (CAS) in conjuction with this course.

Lecture Hours: 45

Evaluation Scheme:
1. In-Semester Evaluation [50 marks]

2. End Semester Evaluation [50 marks]

ˆ 10 marks for Objective (10 Q. × 0.5 = 5 marks for fill in the blank questions and 10
Q. × 0.5 = 5 marks for multiple choice questions)
ˆ 40 marks for Subjective questions (2 Q. × 8 = 16 marks for long answer questions
and 8 Q. × 3 = 24 marks for short answer questions.)

Approved Date: June 24, 2021

1
Course Contents

Unit 1: Introduction: Modeling Philosophy [6 hours]

1.1 Some known models to illustrate the modeling concepts

1.2 Definition of mathematical model and mathematical modeling

1.3 Classification of mathematical modeling

1.4 Steps in building mathematical modeling

1.5 Limitations of mathematical modeling

Unit 2: Modeling Change [8 hours]

2.1 Modeling using proportionality

2.2 Modeling change with difference equations

2.3 Approximating change with difference equations

2.4 Solutions to dynamical systems

2.5 Systems of difference equations

Unit 3: Model fitting [8 hours]

3.1 Model fitting and interpolation

3.2 Fitting models to data graphically

3.3 Analytical methods of model fitting

3.4 Choosing a best model

Unit 4: Experimental modeling [6 hours]

4.1 Introduction

4.2 Higher order polynomial models

4.3 Smoothing: Low order polynomial models

Unit 5: Modeling with differential equations [12 hours]

5.1 Autonomous differential equations and stability

5.2 Autonomous system of differential equations and stability

5.3 Population models

5.4 Drug dosage models

5.5 Euler’s method for systems of differential equations

2
 5.6 A Predator-Prey model

5.7 Lotka-Volterra competition model

5.8 Simple epidemic models

Unit 6: Optimization models [5 hours]

6.1 Continuous optimization models

6.2 Discrete optimization models

Recommended Books
1. A First Course in Mathematical Modeling, Frank R. Giordano, William P. Fox, and Steve
B. Horton, Fifth Edition, Brooks/Cole Cengage Learning, 2013.

2. Mathematical Modeling, Mark M. Meerschaert, Fourth Edition, Elsevier, 2014.

3. Mathematical Modelling, J. N. Kapur, New Age International PVT, India.

4. Differential Equations and Boundary Value Problems: Computing and Modeling, C.

Henry Edwards and David E. Penney, Pearson Education.

5. Advanced Engineering Mathematics, Erwin Kryszig, John Wiley & Sons, INC.

6. Mathematical Modeling: Models, Analysis and Applications, Sandip Banerjee, CRC Press,
2014.

3
In semester evaluation
In semester evaluation may be carried out using the following techniques.

ˆ Internal Exams

ˆ Assignments

ˆ Presentation

ˆ Project

ˆ Viva

4
 Kathmandu University
Course of Study
Course Title: Computational Operations Research Level: Undergraduate
Course Code: MATH 304 Credit: 3
——————————————————————————————————————————

Group: B. Sc. Computational Mathematics (III Year - I Semester)

Total Lecture Hours: 45

Course Description:
Computational Operations Research (COR) practitioners model real world systems and analyze
their behavior using a variety of mathematical and computational techniques. Although the
term” Operations Research” stems from a study of military operations conducted during World
War II, the scope of COR today encompasses a variety of problems in business, engineering,
economics, social and physical sciences , airline crew scheduling ,actuator placement in flexible
space structures, efficient image reconstruction, allocation of spare parts, job shop scheduling,
reliability and performance analysis.

Course Objectives:
This course aims at familiarizing the students with computational tools and techniques in the
various optimization methods which are frequently applied to decision-making process and to
provide a formal quantitative approach to problem solving and an intuition about situations
where such an approach is appropriate. The curriculum in Computational Operations Research
(COR) is designed to emphasize:

• Applications to real-world problem

• Computational experiences with both handy solving the problem and specialized software.

• Mathematical modeling and formulations

• Optimization technique and theory

• Simulation technique and theory

• Theory of queue and their applications and their simulation

• Network analysis by using PERT and CPM.

At the same time, the curriculum strives to be flexible after core competencies in the area are
met. The unit wise outline of the course is given below:

Evaluation Scheme:

In-semester Evaluation - 50 marks

End-Semester Evaluation - 50 marks

Approved Date: .............

1
Course Contents

Unit 0: A review of Matrix Algebra [2]

0.1 Vectors: Euclidean n-Space, Vector inequalities

0.2 Linear Combinations of vectors

0.3 Basis, Standard Basis

0.4 Replacement Theorem

0.5 Hyper-planes and Half-spaces

0.6 Convex set and Convex hull

0.7 Inverse of a Matrix

Unit 1: Linear Programming [8]

1.1 Introduction, Historical Background, Application of Linear Programming

1.2 Requirements and Assumption of a Linear Programming

1.3 Formulation technique of LP problems

1.4 Graphical Solution of two variable problems

1.5 Standard form of LP problem. Matrix form of LP problems

1.6 Computational Procedure for simplex method

1.7 Artificial variable technique- Big M- method. , Two phases Simplex Method

1.8 Unbounded solutions. Non-existing feasible solutions

1.9 Definition of the dual problem, General rules for converting any Primal into its Dual

1.10 Fundamental Theorem of Linear Programming, Minimax Theorem

1.11 How to read the solution of the Dual from the final simplex table of the Primal and
conversely. Dual Simplex Method

Use of available software (TORA and Lindo 6.1): [1]

(i) Graphical Solution of LP-problems
(ii) Solution of LP-Problem by Simplex-Method by using Big-M and two-Phase technique
(iii) Interpretation of solution in terms of dual price and reduced cost

Unit 2: Integer Programming [3]

2.1 Introduction, Mathematical Formulation of the problem

2.2 The graphical Method of solution

2.3 The Gomory Approach

2
Use of available software (TORA and Lindo 6.1): [1]
(i) Solution of LP-problem for its integer value by using TORA under Branch and Bound
techniques

Unit 3: Transportation Models [6]

3.1 Introduction, Mathematical formulation, Tabular representation

3.2 Method for initial basic feasible solution, Optimality test

3.3 Shortest Path Problem

3.4 Minimum Spanning Problem

3.5 Transportation algorithm for minimization

3.6 Transportation algorithm for minimization

3.7 Computation demonstration of optimality test

3.8 Degeneracy in Transportation problems

Use of available software (TORA and Lindo 6.1): [1]

(i) Finding the minimum cost of transportation problems
(ii) Finding the route that minimize the cost of transportation

Unit 4: Assignment Model [6]

4.1 Introduction, Mathematical formulation of the Assignment problem.

4.2 Theorem (without proofs), Methods for solving Assignment problems

4.3 Methods for solving Assignment problems

5.4 Assignment solution procedure (Hungarian Assignment methods)

4.5 Unbalanced Assignment problem

4.6 The traveling salesman problem and its formulation

4.7 Solution Procedure

Use of available software (TORA and Lindo 6.1): [1]

(i) Finding the minimum cost of Assignment problems by usig TORA.
(ii) Finding the routes that minimize the cost of assignments by using TORA.

Unit 5: Simulation (Monte-Carlo Technique) [3]

5.1 Introduction, Definitions of Simulation

5.2 Types of Simulation, Use of simulation

5.3 Generator of Random numbers, Monte – Carlo simulation

5.4 Applications of simulation techniques of various problems

Unit 6: Queuing Models [6]

6.1 Introduction, General description of Queue, Characteristic to be studied

3
 6.2 Kendall’s notation for representation, Queuing models

6.3 Classification of Queuing models, Solution of queuing models

Use of available software (TORA and Lindo 6.1): [1]

(i) Finding the waiting number of customers in the queue (ii) Finding the number of customers
in the system (iii) Finding waiting time and system time in the queue and system.

Unit 7: Network Planning [5]

7.1 Introduction, Project scheduling

7.2 The planning stage-Definition of activities

7.3 Graphical representation of events and activities

7.4 The analysis stage-The critical path, Technique for finding the critical path(s)

7.5 Activity float time, Tabular representation of results

7.6 Scheduling the projects, PERT and activity time Estimates

Use of available software (TORA and Lindo 6.1): [1]

(i) Changing the network problem into LP-problems and solve those by LINDO 6.1

Text Books
1. Essentials of Linear programming, Dr. Jit S. Chandan, Dr. Mahendra P. Kawatra, Dr.
Ki Ho Kim, Vikas publishing House Pvt. Ltd., 1994

2. Linear programming and Theory of Games, [Link], Man Mohan, Sultan Chand and
Sons, 1993.

References
1. [Link] ,Linear programming, Narosa publishing House Pvt. Ltd., 1990.

2. Dr. [Link], Operation Research, 1991-1992, Kedar Ram Nath and company, Meerut,
India.

3. P.K. Gupta, Manmohan, Linear Programming and theory of games, 1991, Sultan Chand
and Sons.

4. Prem Kumar Gupta and Dr. [Link], Operations Research,Revised edition 2008.

5. H.A., Taha, Operations Research: Introduction, Macmillan, New York.

6. J.K., Sharma :Operations Research: Theory and Applications, Macmillan India, New
Delhi

Evaluation
Internal Mark: 40 which is distributed as:
Assignments + Internal examinations+ Practical examination (use of Computational software
and results analysis)

4
Final Examination: F.M. 60

1. Objective:
Section “A”: [10Q × 0.5 =5]
Section “B”: [10Q × 0.5 = 5]
2. Subjective:
Section “C”: [3Q × 7=21] with one OR question
Section “D”: [5Q × 5 =25] with one OR question
Section “E”: [ 2Q × 2=4 ]

5
 Kathmandu University
Course of study
Course Title: Combinatorics Level: Undergraduate
Course Code: MATH - 322 Credit: 3
——————————————————————————————————————————

Group(s): CS/CM (III Year - II Semester)

Prerequisite: MCSC - 201

Objectives:
To impart a basic understanding on the topics of combinatorics, recurrence relation, group
structures with fundamental properties and applications.

Course Contents

Unit 1: Set Theory and Logic [5 hours]

1.1 Set operations, Laws of Set theory, Principle of duality.

1.2 Indexed set, Generalized De Morgan’s Laws.

1.3 Laws of logic and Methods of Proof with Examples.

Unit 2: Properties of Integers: Mathematical Induction [10 hours]

2.1 The Well-ordering Principle: Mathematical Induction.

2.2 Proof of Mathematical Induction: Strong form with Examples.

2.3 Recursive definition, Division Algorithm theorem with Proof.

2.4 The Greatest Common Divisor (GCD): The Euclidean Algorithm with properties.

2.5 The fundamental theorem of Arithmetic: Diophantine equation & Integer solutions.

Unit 3: Elementary Combinatorics [10 hours]

3.1 Basic of Counting: Permutations & Combinations.

3.2 Enumeration of Combinations & Permutations.

3.3 Enumerating Combinations & Permutations with repetitions.

3.4 The Binomial and Multinomial Theorems and associated properties.

3.5 Functions for Computers, The Principle of inclusion and exclusion.

Revised and Approved on March 27, 2016

1
Unit 4: Recurrence relations [10 hours]
4.1 Generating functions of Sequences.

4.2 Partitions of integers, Exponential generating functions.

4.3 Calculating coefficients of generating functions.

4.4 Recurrence relations and solving these by the methods of substitution and generating
functions.

4.5 The method of characteristic roots: Second order linear homogeneous with constant co-
efficients.

4.6 Solution of non-homogeneous recurrence relations.

Unit 5: Groups [10 hours]

5.1 Definitions of group and subgroups with associated properties.

5.2 Homomorphism and Isomorphism on groups.

5.3 Cyclic groups with properties.

5.4 Permutation groups with Examples.

5.5 Cosets and Lagrange’s Theorem.

5.6 Counting and equivalence: Burnside’s Theorem.

Text Books
1. Ralph P. Grimaldi, Discrete and Combinatorial Mathematics, 4th Edition, Pearson Edu-
cation, 2002.

2. Joe L. Mott, Abraham Kandel and Theodore P. Baker, Discrete Mathematics for Com-
puter Scientists and Mathematicians, PHI, New Delhi, 2008.

Reference Books
1. Larry J. Gerstein, Introduction to Mathematical Structures and Proofs, 2nd Edition,
Springer, 2012.

2. K. D. Joshi, Foundations of Discrete Mathematics, New Age International, PVT, New

Delhi.

3. Thomas Koshy, Discrete Mathematics with Applications, Elsevier, 2009.

4. Kenneth H. Rosen, Discrete Mathematics and Its Applications with Combinatorics and
Graph Theory, 7th Edition, McGraw Hill, 2011.

2
 Kathmandu University
Course of study
Course Title: Ordinary and Partial Differential Equations Level: Undergraduate
Course Code: MATH - 217 Credit: 3
——————————————————————————————————————————

Group(s): CM/AP (II Year - II Semester)

Course Description: This course includes ordinary and partial differential equations. ODE
- first order and first degree, first order but not first degree, higher order differential equations,
system of two linear differential equations with constant coefficients and applications of these
ODEs in Physics, Engineering and Bio-Sciences. An introduction of PDE and some second
order PDE in two independent variables as 1D heat and 1D wave equations.

Objectives:

Upon the completion of this course, students will be able to

1. know some methods for the solution of differential equations - both ODE and PDE.

2. use the differential equations in applicable problems.

3. model a simple Physical, Engineering and Biological systems for first and second order
differential equations.

4. visualize solutions and applicable problems using computer.

Course Contents

Unit 1: First order differential equations [10 hours]

1.1 Introduction - Definition, order, degree, linear and nonlinear differential equations, homo-
geneous and nonhomogeneous equations, initial and boundary value problems.

1.2 Solution - Definition, general, particular and singular solution.

1.3 Existence and uniqueness theorem (Statement only), Related problems, direction field.

1.4 Solution methods

1.4.1 First degree - separable, reducible into separable form, exact and criterion for exact
differential equation theorem (proof), reducible into exact form, linear and reducible
into linear form (Bernoulli’s equations).
1.4.2 Not of first degree - solvable for p, y and x, Clairaut’s and Lagrange equations.

1.5 Applications - Growth and decay models, Newton’s law of cooling and heating, Series
circuits (RL and RC circuits), Mixture problems (one compartment model).

Unit 2: Second order differential equations [13 hours]

Revised date : March 17, 2019

1
 2.1 Introduction - homogeneous and non-homogeneous equations, linearly independent and
dependent solutions, general solution, Wronskian.

2.2 Existence and uniqueness theorem (statement only), Superposition principle(proof), Abel’s
formula (proof), Linearly independent and dependent theorem with regard to wronskian
(statement only), LI and general solution theorem (proof).

2.3 General solution of second order linear homogeneous differential equations with constant
coefficients.

2.4 General solution of second order linear non-homogeneous differential equations with con-
stant coefficients.

2.4.1 Method of Variation of parameters.

2.4.2 Method of undetermined coefficients.

2.5 Variable coefficients - Euler-Cauchy equation.

2.6 General solution of higher order linear differential equations with constant coefficients -
Simple problems.

2.7 Applications - Spring mass balance system, LRC-series circuit.

Unit 3: System of two linear differential equations with constant coefficients

[10 hours]
3.1 Introduction - homogeneous and non-homogeneous systems, solution, LI and LD, Wron-
skian, general and particular solutions.

3.2 Linear system theory - Existence and uniqueness theorem (statement only), Superposi-
tion principle (statement only), Abel’s formula (proof), LI, LD and wronskian theorem
(statement only), LI and general solution theorem (statement only).

3.3 Solution methods for homogeneous system

3.3.1 Elimination method.

3.3.2 Determinant method.

3.4 Solution of non-homogeneous system - Simple problems.

3.5 Application - Mixture problem (two compartments).

Unit 4: Partial differential equations [12 hours]

4.1 Introduction - Definition, homogeneous and non-homogeneous, linear and nonlinear PDE,
Some well known PDEs.

4.2 Classification of second order PDE with two independent variables, Superposition principle
(proof).

4.3 Solution methods - by direct integration, PDE solvable as ODE, Separation of variables,
D’Alembert’s method (characteristic equation, normal form).

4.4 1D wave equation with ICs and Dirichlet BCs - D’Alembert’s and separation of variable
methods.

2
 4.5 1D heat equation with IC and Dirichlet BCs - Separation of variable method.

4.6 Laplace equation - Dirichlet BCs with one side of rectangular R kept at potential f (x)
and other sides are grounded.

Text Books
1. C. H. Edwards, D. E. Penney and D. T. Calvis, Differential Equations and Boundary
Value Problems: Computing and Modeling, Pearson Education, 2015.

2. Derrick and Grossman, A First Course in Differential Equations with Applications, 3rd
Edition, CBS Publishers & Distributors.

3. Erwin Kreyszig, Advanced Engineering Mathematics, Wiley & Sons, Inc.

4. Zafar Ahsan, Differential Equations and their Applications, PHI.

3
 Kathmandu University
Course of study for Mathematics

Course Title:Complex Variables Level: Undergraduate

Course Code: MATH - 326 Credit: 3
—————————————————————————————————————————————
This course is offered to [Link]. in Computational Mathematics.

Course Description: This course includes the complex plane, along with the algebra and geometry
of complex numbers, analytic functions, elementary functions such as exponential function, logarithmic
function, trigonometric and hyperbolic functions and their mapping, complex integration, series, residue
and poles with some evaluation of integrals like improper integrals and definite integrals of sine and
cosine functions.

Objectives:

Upon the completion of this course, students will be able to

1. know the basic of elementary complex valued functions and their mapping.

2. understand fundamental concept of complex variable theory.

3. solve different complex integration, real integrals and some specific definite integrals of trigonomet-
ric functions.

Course Contents

Unit 1: Algebra of Complex Numbers [4 hours]

1.1 Complex numbers, Triangle inequality and Its applications

1.2 Polar and exponential forms, Powers and Roots

1.3 Extended complex plane

Unit 2: Analytic Functions [8 hours]

2.1 Functions of a complex variable, Mappings,

2.2 Limits, Theorems of limits without proof, Continuity, Derivatives, Differentiation formula,

2.3 Cauchy-Riemann equations (proof) Sufficient conditions

2.4 Cauchy-Riemann equations in polar form,

2.5 Harmonic functions

Unit 3: Elementary Functions [6 hours]

3.1 Exponential function, Trigonometric functions and Hyperbolic functions

3.2 Logarithmic function

3.3 Complex exponents

August 2019

1
 3.4 Inverse trigonometric and hyperbolic functions

Unit 4: Mappings by Elementary Functions [6 hours]

1
4.1 Linear functions, the function Z

4.2 Linear fractional transformations

4.3 The functions w = z n , w = exp(Z)
4.4 Special linear fractional transformations

Unit 5: Integrals [8 hours]

5.1 Definite integrals, Contours, Line integrals
5.2 Cauchy integral theorem (proof)
5.3 Cauchy integral formula (proof)
5.4 Derivatives of analytic functions(proof)
5.5 Liouville’s theorem, Maximum moduli of functions (proofs)

Unit 6: Series [7 hours]

6.1 Convergence of sequences and series (theorems without proofs)
6.2 Taylor’s series and Its applications
6.3 Laurent’s series, The principle part of a function and Its applications
6.4 Poles, Zero’s of analytic functions

Unit 7: Residues and Poles [6 hours]

7.1 Residues, Proof of Cauchy residue theorem and Its applications
7.2 Evaluation of improper real integrals
7.3 Improper integrals involving Sine and Cosine functions
7.4 Definite integrals of Sine and Cosine functions

Text Books
1. James Ward Brown and Ruel V. Churchill, Complex Variables and Applications, McGraw–Hill
International
2. Advanced Engineering Mathematics, 10th Edition, Erwin Kreyszig, Wiley India Edition.

Reference Books
1. Complex Variables and Their Applications, A. D. Osborne, Addison Wesley Longman, 1999.
2. Complex Variables with Applications, Second Edition, A. D. Wunsch, Addison Wesley Publishing
Company, 1994.
3. Functions of a Complex Variables, B. S. Tyagi, Kedar Nath Ram Nath, Meerut, India.
4. Functions of a Complex Variables, J. K. Goyal and K. P. Gupta, Pragati Prakashan, Meerut India.

2
 Department Of Computer Science and Engineering
Kathmandu University
Dhulikhel, Kavre

Subject: Discrete Mathematics Course: MCSC – 201

Level: [Link]/2​nd​ Year/1​st​ Semester Credit Hours: 3

Course Description: The course attempts to provide discrete methods that stress in many
problems and structures of computer engineering. The course includes concepts of Logic,
Relations and digraph, Graph theory and Algebraic structure.

Course Objectives:​ Broadly, the following are the objectives of this course
● Development of conceptual ideas on the topics.
● Imparting problem solving skills.

Internal Exam : 25 marks

End Semester Evaluation: 75 marks
Objective 20 marks (10 marks fill in the blank and 10 marks for multiple choices)
Subjective 55 marks (Long answer questions 3 Q. × 7 = 21 marks;
Short answer questions 6 Q. × 4 = 24 marks;
Very short answer questions 5 Q × 2 = 10 marks;)

1. Fundamentals [5]
● Algebra on Sets, Sequences, Integers and divisibility, Boolean Matrices,
Mathematical structures

2. Logic [8]
● Propositions and Logical Operations, Conditional Statements, Methods of Proof,
Mathematical induction, Pigeonhole Principle

3. Relations and Diagraphs [8]

● Product Sets and Partitions, Relations and Diagraphs, Paths in Relations and
Diagraphs, Properties of Relations, Equivalence Relations, Operations on
Relations

4. Functions [4]
● Introduction of Functions, Functions for Computer Science, Permutation
Functions
 5. Order Relations and Structures [6]
● Partially Ordered Sets, Extremal Elements of Partially Ordered Sets, Lattices,
Finite Boolean Algebras

6. Graph Theory [9]

● Introduction of Graphs, Subgraphs and Quotient graphs, Euler Paths and circuits,
Hamiltonian paths and circuits, Transport Networks.

7. Semigroups and Groups [8]

● Binary Operations, Semigroups, Product and Quotients of Semigroup, Groups,
Products and Quotients of Groups, Other Mathematical Structures

Text Book:
1. B. Kolman, R. C. Busby and S. C. Ross, Discrete Mathematical Structure, 6th Edition,
PHI, New Delhi.

References:
1. K. Rossen, Discrete Mathematics and Its Applications, 7th Edition, Tata McGrawHill,
New Delhi.
2. R. P. Grimaldi, Discrete and Combinatorial Mathematics, Pearson Education
 Revision approved by Math Subject committee meeting on April 22, 2018

NUMERICAL METHODS

Subject: Numerical Methods

Course: MCSC – 202
Level: [Link]./B.E./[Link]. 2nd Year/2nd Semester
Credit Hours: 3

The course will introduce the fundamentals of numerical methods for engineering and applied science streams. The goal
of the course is to provide a broad background in numerical methods with theoretical discussion and available computer
programming language for theoretical components discussed in the class. Topics include basic introduction to
programming language used for the course, errors in numerical computation, root finding for algebraic (linear and non-
linear equations) and transcendental equation, interpolation, integration of IVP of ODE, solving IVP for ODE, numerical
differentiation, solution of system of linear equations and curve fitting.

Homework Policy
Homework assignment will be given over the course of the semester after the end of each chapter. These will serve
primarily for helping students to practice theoretical components of the course material and programming these
components. Homework will be due one week after it is assigned.

Computer Lab work Policy

There will be some introductory classes for the Programming language introduced as per required by the course. Then the
students will assign lab task for the theoretical components discussed in chapters from 2 to 8 of the course in the class
and will ask to check the numerical results of some of the problems obtained by the concept of theoretical discussion and
by the programming.

Lecture Hours: 45 (Excluding the LAB hours. There will be 1 hour classes for LAB in a week. So, there will be a total
of 4 (3 Theory + 1 Lab) hour classes in a week).

Evaluation Scheme:
 Continue in-Semester Evaluation:
(a) Internal Exam: 20 marks
(b) Computer Lab : 20 marks
 End Semester Evaluation: 60 marks (10 marks for Objective (10Q. × 0.5 = 5 marks fill in the blank
and 10Q. × 0.5 = 5 marks for multiple choices) + 50 marks for Subjective (6 Q × 7 = 42 marks for
long questions and 4 Q × 2 = 8 marks for short questions)).

_________________________________________________________________________________________________

1. Basic introduction of Computer programming language [4]

Course goals and organization
Introduction to Numerical methods
Basic introduction of programming language
2. Errors in numerical computation [5]
Mathematical preliminaries (statement only)
Exact and approximate numbers
Significant digits
Error
Absolute, relative and percentage errors
Absolute error for the sum, product and quotient of any two numbers
Upper limit for absolute error
General error formula
3. Root findings [7]
Introduction
Bisection method
The Secant method
False position method (The Regula-Falsi method)
- Convergence of False Position method and Secant method
Newton – Raphson method
- Quadratic convergence of Newton - Raphson method
- Generalised Newton – Raphson method
The General Iteration method
- Linearly convergence of iteration method
- Acceleration of convergence (Aitken’s 2- process)
Solution to system of nonlinear equations
 – Iteration method
– Newton-Raphson method
4. Finite differences and Interpolation [8]
Finite differences
- forward difference
- backward difference
- central difference
Detection of errors by the use of difference tables
Differences of a polynomial
Introduction for interpolation
Linear and quadratic interpolation and its extension for Newton interpolation formulae (Forward and backward)
Central difference interpolation formulae (Derivation not required)
- Gauss’s, Sterling’s, Bessel’s and Everett’s formulae
- p-value or interval for p-value for the above formulae
Lagrange interpolation formula and its inverse interpolation formula
Divided differences
- Newton’s general interpolation formula
5. Solving ODE (IVP) [6]
Introduction
Solution based on
- Series solution method (Taylor and Picard)
- Tabulated values (Euler, Modified Euler and Runge-Kutta method of second and fourth order)
Solution of BVP using Finite difference method

6. Numerical Differentiation and Integration [7]

Introduction
Numerical differentiation based on interpolation
- Using Newton’s forward difference interpolation formula
- Using Newton’s backward difference interpolation formula
Numerical integration based on interpolation (Derivation using Newton’s forward difference formula)
- Trapezoidal rule
- Simpson’s 1/3 rule
- Simpson’s 3/8 rule
Numerical double integration
- Trapezoidal rule
- Simpson’s rule

7. Matrices and System of linear equations [6]

Review of matrices
Consistency of a linear system of equations
Solution of linear system of equations
- LU decomposition method
- Tri-diagonal system method
- Iterative method (Gauss-Jacobi method and Gauss Siedel method)
8. Curve fitting [2]
Introduction
Least square fitting:
- Straight line fitting
- Non linear fitting (power function, polynomial of nth degree, exponential function)

Recommended Text Book

Introductory Methods of Numerical analysis, S. S. Sastry, PHI Learning Private Limited, New Delhi, 5th
edition, 2012.

Supplementary Text Book

Numerical Methods for Scientific and Engineering computation, M. K. Jain, S. R. K Iyengar & R. K. Jain,
New Age International Publisher, 4th edition, 2005.
 Kathmandu University
Course of study
Course Title: Modern Algebra Level: Undergraduate
Course Code: MATH - 402 Credit: 3
——————————————————————————————————————————

Group: CM (IV Year - I Semester)

Prerequisite: MATH - 322

Course Description:
The course will discuss basic theory of groups, rings, integral domains, fields, extension fields,
finite fields and their applications on cryptography and coding theory.

Technology:
We will use available computer algebra system to understand, construct and verify examples
and theorems on groups, rings, fields and related structures.

Lecture Hours: 45

Evaluation Scheme:
1. In-Semester Evaluation [50 marks]

2. End Semester Evaluation [50 marks]

• 10 marks for Objective (10Q. × 0.5 = 5 marks for fill in the blank questions and
10Q. × 0.5 = 5 marks for multiple choice questions)
• 40 marks for Subjective questions(2Q. × 8 = 16 marks for long answer questions and
8Q. × 3 = 24 marks for short answer questions.)

Course Contents

Unit 1: Groups [8 hours]

1.1 Review of Group theory (Cyclic Groups, Permutation Groups, Cosets, homomorphism
and isomorphism)

1.2 Direct products

1.3 Normal subgroups

1.4 Factor groups

1.5 Simple groups

Revised and Approved on

1
Unit 2: Rings [7 hours]
2.1 Rings
2.2 Integral domains
2.3 Fields
2.4 Cryptography: The RSA cryptosystem

Unit 3: Polynomial rings [5 hours]

3.1 Polynomial rings
3.2 Factorization of polynomials
3.3 Irreducible polynomials

Unit 4: Factor rings [7 hours]

4.1 Ring homomorphism and isomorphism
4.2 Ideals
4.3 Factor rings
4.4 Prime and maximal ideals

Unit 5: Integral domains [6 hours]

5.1 Factorization in integral domains
5.2 Unique factorization domains
5.3 Principal ideal domains
5.4 Euclidean domains

Unit 6: Fields [12 hours]

6.1 Algebraic and transcendental elements
6.2 Irreducible polynomials over field
6.3 Extension fields
6.4 Finite Fields
6.5 Application: Error correcting codes

Recommended Books
1. Abstract Algebra: Theory and Applications, Thomas W. Judson.
(Free book: [Link]
2. A First Course in Abstract Algebra, John B. Fraleigh, Pearson education, 7th edition.
3. Abstract Algebra, David S. Summit and Richard M. Foote, Wiley India, 2nd edition.
4. Topics in algebra, I. N. Herstein, Wiley India, 2nd edition.

2
 Kathmandu University Course
of study
Course Title: Number Theory Level: Undergraduate
Course Code: MATH - 327 Credit: 3

—————————————————————————————————————————
—
Group: CM (III Year – II Semester)

Course Description:

The course will discuss prime numbers and its properties, theory of congruence, Fermat’s theorem,
number- theoretic function, primitive roots and indices and their applications on cryptography
(including Caesar Cipher & RSA)

Technology:
Students will learn/use available computer software to solve number
theory problems.

Lecture Hours: 45

Evaluation Scheme:
1. Continue in-Semester Evaluation [40 marks]
●​ Internal Exam: 20 marks
●​ Assignments: 5 marks
●​ Lab/Project : 15 marks
2 End Semester Evaluation [60 marks]
●​ 10 marks for Objective ( 10 Q. × 0.5 = 5 marks fill in the blank and
10 Q. × 0.5 = 5 marks for multiple choices)
●​ 50 marks for Subjective ( 6 Q. × 7 = 42 marks for long questions and
4 Q. × 2 = 8 marks for short questions)

Course Contents

Unit 1: Prime Number and its Properties [7]

Unit 2: Theory of Congruence [8]

Unit 3: Fermat’s Theorem[7]

Unit 4: Number-Theoretic Functions [9]

Unit 5: Primitive Roots and Indices [9]

Unit 6: Introduction to Cryptography [5]

Recommended Text Book

1. Elementary Number Theory, David M. Burton, Seventh Edition.

Reference Books

1. Elementary Number Theory and its Applications, Kenneth H. Rosen, Addison-Wesley.

2. An Introduction to the Theory of Numbers, Niven Ivan, Herbert S. Zuckerman and Hugh L.
Montgomery.

3. An Introduction to the theory of Numbers, Hardy G.H and Edward M. Wright.

 Department Of Computer Science and Engineering
Kathmandu University
Dhulikhel, Kavre

Subject: Algorithms and Complexity Course Code: COMP 314

Level: B.E./[Link] 3rd Year/2nd Semester Credit Hours: 3

Course Description
This course will introduce students to various algorithm design techniques, and some
intermediate and advanced data structures. It covers some standard algorithms to facilitate
students in understanding algorithm design strategies and algorithm complexity analysis. It also
introduces students to computational complexity issues.

Course Objectives
● Develop a broad understanding of standard algorithm design strategies
● Be familiar with intermediate and advanced data structures and their common uses
● Be able to analyze the asymptotic performance of a variety of algorithms
● Be able to experimentally test the performance of a particular algorithm in a particular
context
● Develop a degree of fluency in the mathematical techniques used to demonstrate
correctness
● Develop and implement algorithms needed in disciplined problem solving
● Develop an understanding of NP-complete (hard) problems and approximation
algorithms

Prerequisites
It is expected that students have been introduced to some prior courses on programming and data
structures (e.g. COMP 202 course). For the understanding and implementation of algorithms, it is
essential that students have a fairly good command of some high level programming languages
like C, C++ or Java.

CHAPTERS
1. Introduction to algorithms [8 Hrs.]
1.1. Mathematical preliminaries of foundations:
 1.1.1. Growth of functions,
1.1.2. Summations,
1.1.3. Recurrences
1.2. Analysis of sorting algorithms
1.2.1. Selection sort
1.2.2. Insertion sort
1.2.3. Merge sort
1.2.4. Quick sort
1.2.5. Heap sort

2. Some data structures [10 Hrs.]

1. Data Structures Basics: Stack, Queue, Linked List, Binary Search Tree.
2. Efficient binary search trees - AVL tree, Red-Black trees
3. Multiway search trees - B-tree, B+-tree
4. Priority queues - Binomial heap, Fibonacci heap
5. Graph data structure - representation, traversal

2. Algorithmic Strategies [12 Hrs.]

2.1. Brute-force algorithms,
2.2. Greedy algorithms:
2.2.1. Action-selection problem
2.2.2. Huffman coding
2.2.3. Minimum spanning tree algorithms - Kruskal’s, Prim’s
2.2.4. Shortest path algorithm - Dijkstra’s
2.2.5. Flow networks - Ford Fulkerson algorithm
2.3. Divide and Conquer,
2.4. Backtracking - N-queen problem
2.5. Branch-and-bound - 0/1 Knapsack problem

3. Dynamic Programming [4 Hrs.]

3.1. Matrix chain multiplication method
3.2. Longest common subsequence

4. Probabilistic and Parallel algorithms [8 Hrs.]

4.1. Probabilistic algorithms
4.1.1. Monte Carlo algorithm - Primality testing
4.1.2. Las Vegas algorithm - N-queen problem
 4.2. Parallel algorithms
4.2.1. Finding connected components in a graph
4.2.2. Parallel sorting

5. NP-Completeness [3 Hrs.]
5.1. NP-completeness and the classes P and NP,
5.2. Polynomial time verification,
5.3. NP-completeness and reducibility,
5.4. NP-complete problems.

Text Books
1. Cormen, Thomas H., Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.
Introduction to algorithms. MIT press, 2009.
2. Horowitz, Ellis, Sahni Sartaj, and Rajasekaran Sanguthevar. Fundamentals of Computer
Algorithms, Second Edition.
3. Goodrich, Michael T., Roberto Tamassia, and Michael H. Goldwasser. Data structures
and algorithms in Python. John Wiley & Sons Ltd, 2013.
4. Necaise, Rance D. Data Structures and Algorithms Using Python. Wiley Publishing,
2010.

Reference Books
1. Aho, Alfred V., and John E. Hopcroft. The design and analysis of computer algorithms,
Fourth Indian Reprint. Pearson Education India, 2001.
2. Goodman, Seymour E., and Stephen T. Hedetniemi. Introduction to the Design and
Analysis of Algorithms. Fifth Printing, 1988.
3. Sahni, Sartaj. Data Structures, Algorithms and Applications in Java. Second Edition.
4. Horowitz, Ellis, Sartaj Sahni, and Susan Anderson-Freed. Fundamentals of data structures
in C. Second Edition.