B.Sc. (Computer Science) Semester 3 Notes 2026

What do you get

• All the notes of all the subjects in Semester 3, as per the latest syllabus 2026.
• Your own dashboard, where you can track everything you have read, subject by subject.
• Valid for one year, 365 days from the day you pay.
• If the University revises the syllabus while your year is running, the notes are rewritten to match and you read the new version at no extra cost. You are never asked to buy the same semester twice.

1. JAVA Programming

   Official Notes munotes.in

   JAVA Programming

   B.SC. (COMPUTER SCIENCE) · SEMESTER 3

   Strictly as per the University of Mumbai NEP syllabus in force for B.Sc. (Computer Science)

   For B.Sc. (Computer Science) students of the University of Mumbai and all its affiliated colleges

   munotes.in Second Year

   JAVA Programming

   Copyright © 2026 munotes.in. All rights reserved.

   Written and first published by munotes.in, 2026.

   This book is free for individual students to read at munotes.in. No part of it may be reproduced, distributed, stored, translated or used for institutional or classroom purposes in any form without a prior written licence from munotes.in.

   Licensing and permissions: contact@munotes.in

   The text of statutes and of judgments reproduced in this book is in the public domain under section 52(1)(q) of the Copyright Act 1957. The commentary, arrangement, examples and questions are the original work of munotes.in.

   munotes.in is an independent study resource for MU students. It is not affiliated with, endorsed by, or officially connected to the University of Mumbai. Course names and university references describe the students and syllabus the material relates to.

   Contents

   Module I Java Basics and OOP, Packages, Exceptions, Multithreading, Collections and JSON

   1. What Java Is, Where It Came From, and Why It Is Still Everywhere 1
   2. The Features of Java, Each One Shown Working 6
   3. The JVM: What Actually Runs Your Program 12
   4. The JDK and the JRE: What You Install, and What Went Away 17
   5. Installing the JDK and Running Your First Program 21
   6. The Structure of a Java Program, Word by Word 26
   7. Tokens: Every Kind of Word a Program Is Made Of 31
   8. Data Types: The Eight Primitives, and What a Reference Is 36
   9. Type Conversion and Casting 42
   10. The Wrapper Classes, Autoboxing and Unboxing 49
   11. Operators, and the Order They Are Applied In 54
   12. Deciding: if, else and switch 61
   13. Repeating: while, do-while, for and the for-each Loop 68
   14. Arrays 74
   15. Strings and the String Class 81
   16. Reading Input: the Scanner and the Command Line 87
   17. Methods 92
   18. The Four Principles of Object-Oriented Programming 98
   19. The Class 103
   20. The Object, the Reference, and the Heap 108

   Contents continued

   Module I continued Java Basics and OOP, Packages, Exceptions, Multithreading, Collections and JSON

   1. Constructors 114
   2. The this Keyword 119
   3. static 123
   4. final 128
   5. Inheritance 133
   6. The super Keyword 141
   7. Polymorphism by Overloading 146
   8. Polymorphism by Overriding, and Dynamic Dispatch 151
   9. Abstraction 157
   10. Encapsulation 162
   11. Abstract Classes 167
   12. Interfaces 172
   13. Inner Classes 178
   14. Anonymous Classes and the Lambda 182
   15. The Object Class: toString, equals and hashCode 188
   16. Predefined Packages and import 194
   17. Writing Your Own Package, and Making a Jar 199
   18. Access Specifiers 204
   19. What an Exception Is, and the Hierarchy 209

   Contents continued

   Module I continued Java Basics and OOP, Packages, Exceptions, Multithreading, Collections and JSON

   1. The Predefined Exceptions, One by One 214
   2. try, catch and finally 219
   3. The throw Statement 225
   4. The throws Clause 230
   5. Writing Your Own Exception 235
   6. What a Thread Is 240
   7. Creating a Thread: Thread and Runnable 245
   8. The Thread Life Cycle 250
   9. Controlling a Thread, and the Three Methods That Are Gone 254
   10. Synchronization, and the Race It Prevents 260
   11. wait, notify and notifyAll: the Producer and the Consumer 266
   12. Deadlock 271
   13. java.util and the Collection Framework 276
   14. Generics, Enough to Use a Collection 281
   15. The Collection Interface and the Iterator 286
   16. The List Interface 291
   17. The Set Interface 295
   18. The Map Interface 299
   19. ArrayList 304

   Contents continued

   Module I continued Java Basics and OOP, Packages, Exceptions, Multithreading, Collections and JSON

   1. LinkedList 308
   2. HashSet 313
   3. TreeSet, Comparable and Comparator 318
   4. HashMap 323
   5. Collections and Arrays: the Utility Methods 328
   6. What JSON Is 333
   7. JSON Syntax, Rule by Rule 337
   8. The JSON Data Types Against Java's 341
   9. JSON with Java 346
   10. How This Paper Is Examined: the Journal, the Write-up and the Viva 350
   11. The Module 1 Practical Set 355

   Module II Swing, JDBC, Servlets, JSP and JSON

   1. The Java Foundation Classes: AWT, Swing and What Came After 363
   2. JFrame: the Window 368
   3. JPanel 373
   4. JButton 377
   5. JTextField and the Text Components 381
   6. JLabel 386

   Contents continued

   Module II continued Swing, JDBC, Servlets, JSP and JSON

   1. The Other Common Swing Components 390
   2. Layouts 395
   3. The Delegation Event Model 401
   4. ActionListener 406
   5. Adapter Classes 411
   6. A Complete Swing Application 416
   7. JDBC Architecture 422
   8. The JDBC Driver Types 427
   9. Connecting to a Database 431
   10. Statement 436
   11. PreparedStatement 440
   12. ResultSet 445
   13. Navigating Data 450
   14. ResultSetMetaData 454
   15. Transactions 459
   16. SQLException 465
   17. A Complete JDBC Program: Create, Read, Update, Delete 471
   18. What a Servlet Is, and What a Container Does 476
   19. Installing Tomcat and Deploying Your First Servlet 480

   Contents continued

   Module II continued Swing, JDBC, Servlets, JSP and JSON

   1. The Servlet Life Cycle 485
   2. The Basic Structure of a Servlet 490
   3. An HTML Form and the Servlet That Answers It 495
   4. The Deployment Descriptor 502
   5. ServletConfig 509
   6. ServletContext 515
   7. RequestDispatcher 522
   8. Response Redirection 528
   9. Session Tracking: Why HTTP Forgets You 535
   10. Cookies 542
   11. URL Rewriting 549
   12. HttpSession 555
   13. The Filter API 564
   14. What a JSP Is, and Its Architecture 572
   15. The JSP Life Cycle 579
   16. Scripting Elements 586
   17. Directives 593
   18. The Implicit Objects 601
   19. Expression Language 607

   Contents continued

   Module II continued Swing, JDBC, Servlets, JSP and JSON

   1. JSTL 614
   2. CRUD with JSP 622
   3. A Session-Managed Web Application, End to End 631
   4. JSON on the Web 641
   5. The JSON Data Types on the Wire 649
   6. JSON with Java: org.json, Gson and Jackson 657
   7. The Module 2 Practical Set 664

   Page 1 onwards

   675 pages in this book. The cover and the contents are above. Everything from page one is in the pass.

   Notes

   2026 Edition, as per the latest syllabus. 675 pages.

   Every chapter in the notes: 120 chapters across 2 modules

   Module I Java Basics and OOP, Packages, Exceptions, Multithreading, Collections and JSON 69 chapters

   1. 1 What Java Is, Where It Came From, and Why It Is Still Everywhere pages 1–5
   2. 2 The Features of Java, Each One Shown Working pages 6–11
   3. 3 The JVM: What Actually Runs Your Program pages 12–16
   4. 4 The JDK and the JRE: What You Install, and What Went Away pages 17–20
   5. 5 Installing the JDK and Running Your First Program pages 21–25
   6. 6 The Structure of a Java Program, Word by Word pages 26–30
   7. 7 Tokens: Every Kind of Word a Program Is Made Of pages 31–35
   8. 8 Data Types: The Eight Primitives, and What a Reference Is pages 36–41
   9. 9 Type Conversion and Casting pages 42–48
   10. 10 The Wrapper Classes, Autoboxing and Unboxing pages 49–53
   11. 11 Operators, and the Order They Are Applied In pages 54–60
   12. 12 Deciding: if, else and switch pages 61–67
   13. 13 Repeating: while, do-while, for and the for-each Loop pages 68–73
   14. 14 Arrays pages 74–80
   15. 15 Strings and the String Class pages 81–86
   16. 16 Reading Input: the Scanner and the Command Line pages 87–91
   17. 17 Methods pages 92–97
   18. 18 The Four Principles of Object-Oriented Programming pages 98–102
   19. 19 The Class pages 103–107
   20. 20 The Object, the Reference, and the Heap pages 108–113
   21. 21 Constructors pages 114–118
   22. 22 The this Keyword pages 119–122
   23. 23 static pages 123–127
   24. 24 final pages 128–132
   25. 25 Inheritance pages 133–140
   26. 26 The super Keyword pages 141–145
   27. 27 Polymorphism by Overloading pages 146–150
   28. 28 Polymorphism by Overriding, and Dynamic Dispatch pages 151–156
   29. 29 Abstraction pages 157–161
   30. 30 Encapsulation pages 162–166
   31. 31 Abstract Classes pages 167–171
   32. 32 Interfaces pages 172–177
   33. 33 Inner Classes pages 178–181
   34. 34 Anonymous Classes and the Lambda pages 182–187
   35. 35 The Object Class: toString, equals and hashCode pages 188–193
   36. 36 Predefined Packages and import pages 194–198
   37. 37 Writing Your Own Package, and Making a Jar pages 199–203
   38. 38 Access Specifiers pages 204–208
   39. 39 What an Exception Is, and the Hierarchy pages 209–213
   40. 40 The Predefined Exceptions, One by One pages 214–218
   41. 41 try, catch and finally pages 219–224
   42. 42 The throw Statement pages 225–229
   43. 43 The throws Clause pages 230–234
   44. 44 Writing Your Own Exception pages 235–239
   45. 45 What a Thread Is pages 240–244
   46. 46 Creating a Thread: Thread and Runnable pages 245–249
   47. 47 The Thread Life Cycle pages 250–253
   48. 48 Controlling a Thread, and the Three Methods That Are Gone pages 254–259
   49. 49 Synchronization, and the Race It Prevents pages 260–265
   50. 50 wait, notify and notifyAll: the Producer and the Consumer pages 266–270
   51. 51 Deadlock pages 271–275
   52. 52 java.util and the Collection Framework pages 276–280
   53. 53 Generics, Enough to Use a Collection pages 281–285
   54. 54 The Collection Interface and the Iterator pages 286–290
   55. 55 The List Interface pages 291–294
   56. 56 The Set Interface pages 295–298
   57. 57 The Map Interface pages 299–303
   58. 58 ArrayList pages 304–307
   59. 59 LinkedList pages 308–312
   60. 60 HashSet pages 313–317
   61. 61 TreeSet, Comparable and Comparator pages 318–322
   62. 62 HashMap pages 323–327
   63. 63 Collections and Arrays: the Utility Methods pages 328–332
   64. 64 What JSON Is pages 333–336
   65. 65 JSON Syntax, Rule by Rule pages 337–340
   66. 66 The JSON Data Types Against Java's pages 341–345
   67. 67 JSON with Java pages 346–349
   68. 68 How This Paper Is Examined: the Journal, the Write-up and the Viva pages 350–354
   69. 69 The Module 1 Practical Set pages 355–362

   Module II Swing, JDBC, Servlets, JSP and JSON 51 chapters

   1. 70 The Java Foundation Classes: AWT, Swing and What Came After pages 363–367
   2. 71 JFrame: the Window pages 368–372
   3. 72 JPanel pages 373–376
   4. 73 JButton pages 377–380
   5. 74 JTextField and the Text Components pages 381–385
   6. 75 JLabel pages 386–389
   7. 76 The Other Common Swing Components pages 390–394
   8. 77 Layouts pages 395–400
   9. 78 The Delegation Event Model pages 401–405
   10. 79 ActionListener pages 406–410
   11. 80 Adapter Classes pages 411–415
   12. 81 A Complete Swing Application pages 416–421
   13. 82 JDBC Architecture pages 422–426
   14. 83 The JDBC Driver Types pages 427–430
   15. 84 Connecting to a Database pages 431–435
   16. 85 Statement pages 436–439
   17. 86 PreparedStatement pages 440–444
   18. 87 ResultSet pages 445–449
   19. 88 Navigating Data pages 450–453
   20. 89 ResultSetMetaData pages 454–458
   21. 90 Transactions pages 459–464
   22. 91 SQLException pages 465–470
   23. 92 A Complete JDBC Program: Create, Read, Update, Delete pages 471–475
   24. 93 What a Servlet Is, and What a Container Does pages 476–479
   25. 94 Installing Tomcat and Deploying Your First Servlet pages 480–484
   26. 95 The Servlet Life Cycle pages 485–489
   27. 96 The Basic Structure of a Servlet pages 490–494
   28. 97 An HTML Form and the Servlet That Answers It pages 495–501
   29. 98 The Deployment Descriptor pages 502–508
   30. 99 ServletConfig pages 509–514
   31. 100 ServletContext pages 515–521
   32. 101 RequestDispatcher pages 522–527
   33. 102 Response Redirection pages 528–534
   34. 103 Session Tracking: Why HTTP Forgets You pages 535–541
   35. 104 Cookies pages 542–548
   36. 105 URL Rewriting pages 549–554
   37. 106 HttpSession pages 555–563
   38. 107 The Filter API pages 564–571
   39. 108 What a JSP Is, and Its Architecture pages 572–578
   40. 109 The JSP Life Cycle pages 579–585
   41. 110 Scripting Elements pages 586–592
   42. 111 Directives pages 593–600
   43. 112 The Implicit Objects pages 601–606
   44. 113 Expression Language pages 607–613
   45. 114 JSTL pages 614–621
   46. 115 CRUD with JSP pages 622–630
   47. 116 A Session-Managed Web Application, End to End pages 631–640
   48. 117 JSON on the Web pages 641–648
   49. 118 The JSON Data Types on the Wire pages 649–656
   50. 119 JSON with Java: org.json, Gson and Jackson pages 657–663
   51. 120 The Module 2 Practical Set pages 664–675

2. Data Structures

   Official Notes munotes.in

   Data Structures

   B.SC. (COMPUTER SCIENCE) · SEMESTER 3

   Strictly as per the University of Mumbai NEP syllabus in force for B.Sc. (Computer Science)

   For B.Sc. (Computer Science) students of the University of Mumbai and all its affiliated colleges

   munotes.in Second Year

   Data Structures

   Copyright © 2026 munotes.in. All rights reserved.

   Written and first published by munotes.in, 2026.

   This book is free for individual students to read at munotes.in. No part of it may be reproduced, distributed, stored, translated or used for institutional or classroom purposes in any form without a prior written licence from munotes.in.

   Licensing and permissions: contact@munotes.in

   The text of statutes and of judgments reproduced in this book is in the public domain under section 52(1)(q) of the Copyright Act 1957. The commentary, arrangement, examples and questions are the original work of munotes.in.

   munotes.in is an independent study resource for MU students. It is not affiliated with, endorsed by, or officially connected to the University of Mumbai. Course names and university references describe the students and syllabus the material relates to.

   Contents

   Module I Abstract Data Type, Linked Structures, Stacks and Queues

   1. What a Data Structure Is, and Why the One You Pick Decides Whether the Program Works 1
   2. How This Paper Is Examined, and How to Read This Book 5
   3. Data and Its Types: What a Type Actually Settles 8
   4. The Primitive Types, and Where They Stop 11
   5. Linear and Non-Linear, Static and Dynamic: The Map of the Subject 14
   6. Choosing a Structure: The Three Questions to Ask of Any of Them 17
   7. The Abstract Data Type: A Promise, and a Hidden Representation 20
   8. Why Hiding the Representation Is the Whole Point 23
   9. Writing an ADT of Your Own 26
   10. Judging an ADT: Complete, Minimal, and Honest About Cost 29
   11. The Array: What It Really Is in Memory 32
   12. Where the Array Stops: Insertion, Deletion and Growth 35
   13. The Linked List: The Node, the Chain and the Head 38
   14. The Linked List ADT, and Building an Empty One 41
   15. Traversing a Singly Linked List 44
   16. Searching a Singly Linked List 47
   17. Prepending a Node 50
   18. Appending a Node, and Why It Costs More 53

   Contents continued

   Module I continued Abstract Data Type, Linked Structures, Stacks and Queues

   1. Removing a Node 56
   2. Inserting and Deleting at Any Position 59
   3. What a Singly Linked List Is Good and Bad At 62
   4. The Array Against the Linked List, Measured 65
   5. A Polynomial as a Linked List 68
   6. Adding Two Polynomials 71
   7. Multiplying Polynomials, and What the Representation Costs 74
   8. The Doubly Linked List: The Second Link 77
   9. Insertion and Deletion With Two Links 80
   10. Traversing Both Ways, and the Applications That Need It 84
   11. What the Second Link Costs and What It Buys 87
   12. The Stack: One End, and Why That Is Enough 90
   13. The Stack ADT: Push, Pop, and the Errors 93
   14. A Stack on an Array, With Peek 96
   15. A Stack on Links 99
   16. What a Stack Is Good and Bad At 102
   17. Balanced Delimiters, and Why a Counter Is Not Enough 105
   18. Infix, Prefix and Postfix 108
   19. Infix to Postfix With a Stack 111

   Contents continued

   Module I continued Abstract Data Type, Linked Structures, Stacks and Queues

   1. Evaluating a Postfix Expression 114
   2. Prefix: Converting to It, and Evaluating It 118
   3. The Queue: Two Ends 122
   4. The Queue ADT 125
   5. A Queue on an Array, and the Drift That Ruins It 128
   6. A Queue on Links 131
   7. The Circular Queue: Wrap-Around 134
   8. Full or Empty: Telling Them Apart 137
   9. What a Queue Is Good and Bad At 140
   10. The Deque: Open at Both Ends 143
   11. Job Scheduling With a Queue 146
   12. Module 1 in One Sitting 149

   Module II Trees, Priority Queues and Heaps, Graphs and Hashing

   1. From a Line to a Tree: Why Linear Structures Run Out 153
   2. The Tree ADT: The Words, Said Exactly 156
   3. Height, Depth, Level and Size, and the Relations Between Them 159
   4. What a Tree Buys, and What It Costs 162
   5. The Binary Tree 165

   Contents continued

   Module II continued Trees, Priority Queues and Heaps, Graphs and Hashing

   1. Binary Tree Properties, Proved 168
   2. Full, Complete and Perfect, and Why the Difference Matters 171
   3. Implementing a Binary Tree With Links 174
   4. The Array Representation of a Binary Tree 177
   5. Inorder Traversal 180
   6. Preorder and Postorder Traversal 183
   7. Level Order Traversal, and the Queue It Needs 186
   8. Iterative Traversal, and the Stack It Needs 189
   9. Rebuilding a Tree From Two Traversals 192
   10. The Binary Search Tree: The Invariant 196
   11. Searching a Binary Search Tree 199
   12. Inserting Into a Binary Search Tree 202
   13. Deleting From a Binary Search Tree: The Three Cases 205
   14. Why a Binary Search Tree Degenerates 209
   15. What Balance Means 212
   16. Threaded Binary Trees 216
   17. The AVL Tree and the Balance Factor 220
   18. The Four Rotations 223
   19. Insertion Into an AVL Tree 227

   Contents continued

   Module II continued Trees, Priority Queues and Heaps, Graphs and Hashing

   1. Deletion From an AVL Tree 231
   2. Huffman Coding: The Problem 235
   3. Building the Huffman Tree 238
   4. Why the Huffman Code Is Prefix-Free, and What It Saves 241
   5. The Priority Queue: When First In Is the Wrong Rule 246
   6. The Priority Queue ADT 249
   7. Three Ways to Build One, and What Each Costs 252
   8. The Heap: Shape and Order 255
   9. The Array That Holds a Heap 258
   10. Min-Heap and Max-Heap 262
   11. Heapify: Sifting Up and Sifting Down 265
   12. Building a Heap, and Why It Is Linear 269
   13. Where Priority Queues Are Used 273
   14. What a Graph Is 276
   15. The Vocabulary of Graphs 279
   16. The Graph ADT 282
   17. The Adjacency Matrix 285
   18. The Adjacency List 288
   19. Which Representation: The Costs, Measured 291

   Contents continued

   Module II continued Trees, Priority Queues and Heaps, Graphs and Hashing

   1. Inserting and Deleting Vertices and Edges 296
   2. Breadth First Search 302
   3. Depth First Search 307
   4. Connectivity and Connected Components 312
   5. The Shortest Path in an Unweighted Graph 317
   6. Dijkstra's Algorithm 321
   7. The Idea of Hashing: A Key Turned Into an Address 328
   8. The Hash Table ADT 334
   9. Hash Functions 339
   10. What Makes a Hash Function Good 348
   11. Collisions Are Certain, Not Unlucky 354
   12. Chaining 361
   13. Linear Probing 367
   14. Quadratic Probing and Double Hashing 376
   15. Load Factor and Rehashing 384
   16. What Hashing Buys and What It Gives Up 391
   17. Where Hashing Is Used, and Where It Must Not Be 396
   18. Choosing the Right Structure: The Whole Paper on One Page 402
   19. Module 2 in One Sitting 407

   Page 1 onwards

   411 pages in this book. The cover and the contents are above. Everything from page one is in the pass.

   Notes

   2026 Edition, as per the latest syllabus. 411 pages.

   Every chapter in the notes: 111 chapters across 2 modules

   Module I Abstract Data Type, Linked Structures, Stacks and Queues 49 chapters

   1. 1 What a Data Structure Is, and Why the One You Pick Decides Whether the Program Works pages 1–4
   2. 2 How This Paper Is Examined, and How to Read This Book pages 5–7
   3. 3 Data and Its Types: What a Type Actually Settles pages 8–10
   4. 4 The Primitive Types, and Where They Stop pages 11–13
   5. 5 Linear and Non-Linear, Static and Dynamic: The Map of the Subject pages 14–16
   6. 6 Choosing a Structure: The Three Questions to Ask of Any of Them pages 17–19
   7. 7 The Abstract Data Type: A Promise, and a Hidden Representation pages 20–22
   8. 8 Why Hiding the Representation Is the Whole Point pages 23–25
   9. 9 Writing an ADT of Your Own pages 26–28
   10. 10 Judging an ADT: Complete, Minimal, and Honest About Cost pages 29–31
   11. 11 The Array: What It Really Is in Memory pages 32–34
   12. 12 Where the Array Stops: Insertion, Deletion and Growth pages 35–37
   13. 13 The Linked List: The Node, the Chain and the Head pages 38–40
   14. 14 The Linked List ADT, and Building an Empty One pages 41–43
   15. 15 Traversing a Singly Linked List pages 44–46
   16. 16 Searching a Singly Linked List pages 47–49
   17. 17 Prepending a Node pages 50–52
   18. 18 Appending a Node, and Why It Costs More pages 53–55
   19. 19 Removing a Node pages 56–58
   20. 20 Inserting and Deleting at Any Position pages 59–61
   21. 21 What a Singly Linked List Is Good and Bad At pages 62–64
   22. 22 The Array Against the Linked List, Measured pages 65–67
   23. 23 A Polynomial as a Linked List pages 68–70
   24. 24 Adding Two Polynomials pages 71–73
   25. 25 Multiplying Polynomials, and What the Representation Costs pages 74–76
   26. 26 The Doubly Linked List: The Second Link pages 77–79
   27. 27 Insertion and Deletion With Two Links pages 80–83
   28. 28 Traversing Both Ways, and the Applications That Need It pages 84–86
   29. 29 What the Second Link Costs and What It Buys pages 87–89
   30. 30 The Stack: One End, and Why That Is Enough pages 90–92
   31. 31 The Stack ADT: Push, Pop, and the Errors pages 93–95
   32. 32 A Stack on an Array, With Peek pages 96–98
   33. 33 A Stack on Links pages 99–101
   34. 34 What a Stack Is Good and Bad At pages 102–104
   35. 35 Balanced Delimiters, and Why a Counter Is Not Enough pages 105–107
   36. 36 Infix, Prefix and Postfix pages 108–110
   37. 37 Infix to Postfix With a Stack pages 111–113
   38. 38 Evaluating a Postfix Expression pages 114–117
   39. 39 Prefix: Converting to It, and Evaluating It pages 118–121
   40. 40 The Queue: Two Ends pages 122–124
   41. 41 The Queue ADT pages 125–127
   42. 42 A Queue on an Array, and the Drift That Ruins It pages 128–130
   43. 43 A Queue on Links pages 131–133
   44. 44 The Circular Queue: Wrap-Around pages 134–136
   45. 45 Full or Empty: Telling Them Apart pages 137–139
   46. 46 What a Queue Is Good and Bad At pages 140–142
   47. 47 The Deque: Open at Both Ends pages 143–145
   48. 48 Job Scheduling With a Queue pages 146–148
   49. 49 Module 1 in One Sitting pages 149–152

   Module II Trees, Priority Queues and Heaps, Graphs and Hashing 62 chapters

   1. 50 From a Line to a Tree: Why Linear Structures Run Out pages 153–155
   2. 51 The Tree ADT: The Words, Said Exactly pages 156–158
   3. 52 Height, Depth, Level and Size, and the Relations Between Them pages 159–161
   4. 53 What a Tree Buys, and What It Costs pages 162–164
   5. 54 The Binary Tree pages 165–167
   6. 55 Binary Tree Properties, Proved pages 168–170
   7. 56 Full, Complete and Perfect, and Why the Difference Matters pages 171–173
   8. 57 Implementing a Binary Tree With Links pages 174–176
   9. 58 The Array Representation of a Binary Tree pages 177–179
   10. 59 Inorder Traversal pages 180–182
   11. 60 Preorder and Postorder Traversal pages 183–185
   12. 61 Level Order Traversal, and the Queue It Needs pages 186–188
   13. 62 Iterative Traversal, and the Stack It Needs pages 189–191
   14. 63 Rebuilding a Tree From Two Traversals pages 192–195
   15. 64 The Binary Search Tree: The Invariant pages 196–198
   16. 65 Searching a Binary Search Tree pages 199–201
   17. 66 Inserting Into a Binary Search Tree pages 202–204
   18. 67 Deleting From a Binary Search Tree: The Three Cases pages 205–208
   19. 68 Why a Binary Search Tree Degenerates pages 209–211
   20. 69 What Balance Means pages 212–215
   21. 70 Threaded Binary Trees pages 216–219
   22. 71 The AVL Tree and the Balance Factor pages 220–222
   23. 72 The Four Rotations pages 223–226
   24. 73 Insertion Into an AVL Tree pages 227–230
   25. 74 Deletion From an AVL Tree pages 231–234
   26. 75 Huffman Coding: The Problem pages 235–237
   27. 76 Building the Huffman Tree pages 238–240
   28. 77 Why the Huffman Code Is Prefix-Free, and What It Saves pages 241–245
   29. 78 The Priority Queue: When First In Is the Wrong Rule pages 246–248
   30. 79 The Priority Queue ADT pages 249–251
   31. 80 Three Ways to Build One, and What Each Costs pages 252–254
   32. 81 The Heap: Shape and Order pages 255–257
   33. 82 The Array That Holds a Heap pages 258–261
   34. 83 Min-Heap and Max-Heap pages 262–264
   35. 84 Heapify: Sifting Up and Sifting Down pages 265–268
   36. 85 Building a Heap, and Why It Is Linear pages 269–272
   37. 86 Where Priority Queues Are Used pages 273–275
   38. 87 What a Graph Is pages 276–278
   39. 88 The Vocabulary of Graphs pages 279–281
   40. 89 The Graph ADT pages 282–284
   41. 90 The Adjacency Matrix pages 285–287
   42. 91 The Adjacency List pages 288–290
   43. 92 Which Representation: The Costs, Measured pages 291–295
   44. 93 Inserting and Deleting Vertices and Edges pages 296–301
   45. 94 Breadth First Search pages 302–306
   46. 95 Depth First Search pages 307–311
   47. 96 Connectivity and Connected Components pages 312–316
   48. 97 The Shortest Path in an Unweighted Graph pages 317–320
   49. 98 Dijkstra's Algorithm pages 321–327
   50. 99 The Idea of Hashing: A Key Turned Into an Address pages 328–333
   51. 100 The Hash Table ADT pages 334–338
   52. 101 Hash Functions pages 339–347
   53. 102 What Makes a Hash Function Good pages 348–353
   54. 103 Collisions Are Certain, Not Unlucky pages 354–360
   55. 104 Chaining pages 361–366
   56. 105 Linear Probing pages 367–375
   57. 106 Quadratic Probing and Double Hashing pages 376–383
   58. 107 Load Factor and Rehashing pages 384–390
   59. 108 What Hashing Buys and What It Gives Up pages 391–395
   60. 109 Where Hashing Is Used, and Where It Must Not Be pages 396–401
   61. 110 Choosing the Right Structure: The Whole Paper on One Page pages 402–406
   62. 111 Module 2 in One Sitting pages 407–411

3. Principles of Operating Systems

   Official Notes munotes.in

   Principles of Operating Systems

   B.SC. (COMPUTER SCIENCE) · SEMESTER 3

   Strictly as per the University of Mumbai NEP syllabus in force for B.Sc. (Computer Science)

   For B.Sc. (Computer Science) students of the University of Mumbai and all its affiliated colleges

   munotes.in Second Year

   Principles of Operating Systems

   Copyright © 2026 munotes.in. All rights reserved.

   Written and first published by munotes.in, 2026.

   This book is free for individual students to read at munotes.in. No part of it may be reproduced, distributed, stored, translated or used for institutional or classroom purposes in any form without a prior written licence from munotes.in.

   Licensing and permissions: contact@munotes.in

   The text of statutes and of judgments reproduced in this book is in the public domain under section 52(1)(q) of the Copyright Act 1957. The commentary, arrangement, examples and questions are the original work of munotes.in.

   munotes.in is an independent study resource for MU students. It is not affiliated with, endorsed by, or officially connected to the University of Mumbai. Course names and university references describe the students and syllabus the material relates to.

   Contents

   Module I Fundamentals of Operating Systems, Processes and Threads, Process Synchronization, and CPU Scheduling

   1. What an Operating System Is 1
   2. The Two Jobs: Handing Out the Machine, and Hiding It 5
   3. Interrupts, Traps and the Two Modes 9
   4. The Timer, and Why the Operating System Always Gets the Processor Back 14
   5. The Functions of an Operating System 19
   6. Where Operating Systems Run 23
   7. The Services an Operating System Offers 27
   8. The Command Line and the Desktop 31
   9. What a System Call Is 35
   10. Watching System Calls Happen 39
   11. The Six Families of System Call 43
   12. How an Operating System Is Built 46
   13. Microkernels, Modules and What Linux Actually Is 49
   14. What a Process Is 53
   15. The Five States of a Process 57
   16. The Process Control Block 61
   17. The Queues, the Schedulers and the Context Switch 65
   18. Creating a Process: fork 69
   19. Running a Different Program: exec 73
   20. Waiting, Exiting, the Zombie and the Orphan 77

   Contents continued

   Module I continued Fundamentals of Operating Systems, Processes and Threads, Process Synchronization, and CPU Scheduling

   1. Inter-process Communication: The Two Models 81
   2. Shared Memory, in Code That Runs 85
   3. Pipes 89
   4. Message Queues 93
   5. Blocking and Non-blocking Communication 97
   6. What a Thread Is 101
   7. Making Threads, and Waiting for Them 105
   8. Multicore Programming, and the Limit on It 109
   9. The Three Multithreading Models 113
   10. Thread Pools, and Handing Work Out 117
   11. Measuring It: Sequential Against Threaded 121
   12. The Shape of Every Concurrent Program 126
   13. A Race Condition, Made to Happen 130
   14. The Critical Section Problem, and the Three Conditions 135
   15. Peterson's Solution 139
   16. Hardware Help: Test and Set, and Compare and Swap 143
   17. The Mutex Lock 147
   18. The Semaphore 151
   19. The Bounded Buffer, Solved 155

   Contents continued

   Module I continued Fundamentals of Operating Systems, Processes and Threads, Process Synchronization, and CPU Scheduling

   1. The Readers and the Writers 160
   2. The Dining Philosophers 164
   3. Monitors and Condition Variables 169
   4. Why Scheduling Exists: The Burst Cycle 174
   5. The Dispatcher, Preemption, and What a Switch Costs 178
   6. The Five Criteria, and the Arithmetic of Each 182
   7. Reading and Drawing a Gantt Chart 185
   8. First Come First Served 188
   9. Shortest Job First 191
   10. Shortest Remaining Time First 194
   11. Priority Scheduling, Starvation and Ageing 197
   12. Round Robin, and Choosing the Quantum 200
   13. Multilevel Queue Scheduling 203
   14. Multilevel Feedback Queue Scheduling 206
   15. All Seven Algorithms on One Problem 210
   16. Thread Scheduling, and What Linux Actually Does 214

   Module II Deadlocks, Memory Management, Virtual Memory and Mass Storage, and the File System

   1. What a Deadlock Is, and the System Model 218
   2. The Four Conditions 222

   Contents continued

   Module II continued Deadlocks, Memory Management, Virtual Memory and Mass Storage, and the File System

   1. The Resource Allocation Graph 226
   2. The Four Ways to Handle a Deadlock 230
   3. Deadlock Prevention 233
   4. Safe States, and Avoidance 237
   5. The Banker's Algorithm 241
   6. The Resource Request Algorithm 245
   7. Deadlock Detection 249
   8. Recovery from Deadlock 254
   9. Why Memory Needs Managing 258
   10. Binding an Address: Compile, Load, Run 262
   11. The Memory Management Unit 266
   12. Swapping 270
   13. Contiguous Allocation, and the Holes It Leaves 274
   14. First Fit, Best Fit and Worst Fit 278
   15. Fragmentation, Internal and External 282
   16. Segmentation 286
   17. Paging 290
   18. Splitting an Address, and Translating One 295
   19. The TLB, and the Effective Access Time 299

   Contents continued

   Module II continued Deadlocks, Memory Management, Virtual Memory and Mass Storage, and the File System

   1. Protection and Sharing in a Paged System 304
   2. The Page Table Is Too Big: Hierarchical Paging 309
   3. Hashed and Inverted Page Tables 314
   4. Virtual Memory: Running What Will Not Fit 318
   5. Demand Paging, and the Page Fault 323
   6. The Effective Access Time Under Demand Paging 328
   7. Copy on Write 332
   8. Page Replacement: The Problem 337
   9. FIFO Replacement, and Belady's Anomaly 341
   10. Optimal Replacement 345
   11. LRU Replacement 348
   12. Second Chance, and the Counting Algorithms 352
   13. Comparing the Algorithms, and the Hit Ratio 357
   14. Allocation of Frames 361
   15. Thrashing, and the Working Set 365
   16. What a Disk Is, and What It Costs 370
   17. Disk Structure, and the Logical Block 374
   18. Disk Scheduling: FCFS and SSTF 378
   19. SCAN, C-SCAN, LOOK and C-LOOK 382

   Contents continued

   Module II continued Deadlocks, Memory Management, Virtual Memory and Mass Storage, and the File System

   1. Random Scheduling, and All Six Compared 386
   2. Disk Management 389
   3. What a File Is 394
   4. Opening a File, and What the Kernel Keeps 398
   5. Access Methods 402
   6. Directories, and the Shapes They Take 406
   7. Mounting 412
   8. File Sharing, and Locking 416
   9. The Layers a Read Passes Through 421
   10. On the Disk: Superblock, Inode, Data Blocks 425
   11. Directory Implementation 429
   12. Contiguous and Linked Allocation 433
   13. Indexed Allocation, and What a Real File System Does 438
   14. Free Space Management 443
   15. Designing a Small File System 448

   Page 1 onwards

   452 pages in this book. The cover and the contents are above. Everything from page one is in the pass.

   Notes

   2026 Edition, as per the latest syllabus. 452 pages.

   Every chapter in the notes: 110 chapters across 2 modules

   Module I Fundamentals of Operating Systems, Processes and Threads, Process Synchronization, and CPU Scheduling 55 chapters

   1. 1 What an Operating System Is pages 1–4
   2. 2 The Two Jobs: Handing Out the Machine, and Hiding It pages 5–8
   3. 3 Interrupts, Traps and the Two Modes pages 9–13
   4. 4 The Timer, and Why the Operating System Always Gets the Processor Back pages 14–18
   5. 5 The Functions of an Operating System pages 19–22
   6. 6 Where Operating Systems Run pages 23–26
   7. 7 The Services an Operating System Offers pages 27–30
   8. 8 The Command Line and the Desktop pages 31–34
   9. 9 What a System Call Is pages 35–38
   10. 10 Watching System Calls Happen pages 39–42
   11. 11 The Six Families of System Call pages 43–45
   12. 12 How an Operating System Is Built pages 46–48
   13. 13 Microkernels, Modules and What Linux Actually Is pages 49–52
   14. 14 What a Process Is pages 53–56
   15. 15 The Five States of a Process pages 57–60
   16. 16 The Process Control Block pages 61–64
   17. 17 The Queues, the Schedulers and the Context Switch pages 65–68
   18. 18 Creating a Process: fork pages 69–72
   19. 19 Running a Different Program: exec pages 73–76
   20. 20 Waiting, Exiting, the Zombie and the Orphan pages 77–80
   21. 21 Inter-process Communication: The Two Models pages 81–84
   22. 22 Shared Memory, in Code That Runs pages 85–88
   23. 23 Pipes pages 89–92
   24. 24 Message Queues pages 93–96
   25. 25 Blocking and Non-blocking Communication pages 97–100
   26. 26 What a Thread Is pages 101–104
   27. 27 Making Threads, and Waiting for Them pages 105–108
   28. 28 Multicore Programming, and the Limit on It pages 109–112
   29. 29 The Three Multithreading Models pages 113–116
   30. 30 Thread Pools, and Handing Work Out pages 117–120
   31. 31 Measuring It: Sequential Against Threaded pages 121–125
   32. 32 The Shape of Every Concurrent Program pages 126–129
   33. 33 A Race Condition, Made to Happen pages 130–134
   34. 34 The Critical Section Problem, and the Three Conditions pages 135–138
   35. 35 Peterson's Solution pages 139–142
   36. 36 Hardware Help: Test and Set, and Compare and Swap pages 143–146
   37. 37 The Mutex Lock pages 147–150
   38. 38 The Semaphore pages 151–154
   39. 39 The Bounded Buffer, Solved pages 155–159
   40. 40 The Readers and the Writers pages 160–163
   41. 41 The Dining Philosophers pages 164–168
   42. 42 Monitors and Condition Variables pages 169–173
   43. 43 Why Scheduling Exists: The Burst Cycle pages 174–177
   44. 44 The Dispatcher, Preemption, and What a Switch Costs pages 178–181
   45. 45 The Five Criteria, and the Arithmetic of Each pages 182–184
   46. 46 Reading and Drawing a Gantt Chart pages 185–187
   47. 47 First Come First Served pages 188–190
   48. 48 Shortest Job First pages 191–193
   49. 49 Shortest Remaining Time First pages 194–196
   50. 50 Priority Scheduling, Starvation and Ageing pages 197–199
   51. 51 Round Robin, and Choosing the Quantum pages 200–202
   52. 52 Multilevel Queue Scheduling pages 203–205
   53. 53 Multilevel Feedback Queue Scheduling pages 206–209
   54. 54 All Seven Algorithms on One Problem pages 210–213
   55. 55 Thread Scheduling, and What Linux Actually Does pages 214–217

   Module II Deadlocks, Memory Management, Virtual Memory and Mass Storage, and the File System 55 chapters

   1. 56 What a Deadlock Is, and the System Model pages 218–221
   2. 57 The Four Conditions pages 222–225
   3. 58 The Resource Allocation Graph pages 226–229
   4. 59 The Four Ways to Handle a Deadlock pages 230–232
   5. 60 Deadlock Prevention pages 233–236
   6. 61 Safe States, and Avoidance pages 237–240
   7. 62 The Banker's Algorithm pages 241–244
   8. 63 The Resource Request Algorithm pages 245–248
   9. 64 Deadlock Detection pages 249–253
   10. 65 Recovery from Deadlock pages 254–257
   11. 66 Why Memory Needs Managing pages 258–261
   12. 67 Binding an Address: Compile, Load, Run pages 262–265
   13. 68 The Memory Management Unit pages 266–269
   14. 69 Swapping pages 270–273
   15. 70 Contiguous Allocation, and the Holes It Leaves pages 274–277
   16. 71 First Fit, Best Fit and Worst Fit pages 278–281
   17. 72 Fragmentation, Internal and External pages 282–285
   18. 73 Segmentation pages 286–289
   19. 74 Paging pages 290–294
   20. 75 Splitting an Address, and Translating One pages 295–298
   21. 76 The TLB, and the Effective Access Time pages 299–303
   22. 77 Protection and Sharing in a Paged System pages 304–308
   23. 78 The Page Table Is Too Big: Hierarchical Paging pages 309–313
   24. 79 Hashed and Inverted Page Tables pages 314–317
   25. 80 Virtual Memory: Running What Will Not Fit pages 318–322
   26. 81 Demand Paging, and the Page Fault pages 323–327
   27. 82 The Effective Access Time Under Demand Paging pages 328–331
   28. 83 Copy on Write pages 332–336
   29. 84 Page Replacement: The Problem pages 337–340
   30. 85 FIFO Replacement, and Belady's Anomaly pages 341–344
   31. 86 Optimal Replacement pages 345–347
   32. 87 LRU Replacement pages 348–351
   33. 88 Second Chance, and the Counting Algorithms pages 352–356
   34. 89 Comparing the Algorithms, and the Hit Ratio pages 357–360
   35. 90 Allocation of Frames pages 361–364
   36. 91 Thrashing, and the Working Set pages 365–369
   37. 92 What a Disk Is, and What It Costs pages 370–373
   38. 93 Disk Structure, and the Logical Block pages 374–377
   39. 94 Disk Scheduling: FCFS and SSTF pages 378–381
   40. 95 SCAN, C-SCAN, LOOK and C-LOOK pages 382–385
   41. 96 Random Scheduling, and All Six Compared pages 386–388
   42. 97 Disk Management pages 389–393
   43. 98 What a File Is pages 394–397
   44. 99 Opening a File, and What the Kernel Keeps pages 398–401
   45. 100 Access Methods pages 402–405
   46. 101 Directories, and the Shapes They Take pages 406–411
   47. 102 Mounting pages 412–415
   48. 103 File Sharing, and Locking pages 416–420
   49. 104 The Layers a Read Passes Through pages 421–424
   50. 105 On the Disk: Superblock, Inode, Data Blocks pages 425–428
   51. 106 Directory Implementation pages 429–432
   52. 107 Contiguous and Linked Allocation pages 433–437
   53. 108 Indexed Allocation, and What a Real File System Does pages 438–442
   54. 109 Free Space Management pages 443–447
   55. 110 Designing a Small File System pages 448–452

4. Theory of Computation

   Official Notes munotes.in

   Theory of Computation

   B.SC. (COMPUTER SCIENCE) · SEMESTER 3

   Strictly as per the University of Mumbai NEP syllabus in force for B.Sc. (Computer Science)

   For B.Sc. (Computer Science) students of the University of Mumbai and all its affiliated colleges

   munotes.in Second Year

   Theory of Computation

   Copyright © 2026 munotes.in. All rights reserved.

   Written and first published by munotes.in, 2026.

   This book is free for individual students to read at munotes.in. No part of it may be reproduced, distributed, stored, translated or used for institutional or classroom purposes in any form without a prior written licence from munotes.in.

   Licensing and permissions: contact@munotes.in

   The text of statutes and of judgments reproduced in this book is in the public domain under section 52(1)(q) of the Copyright Act 1957. The commentary, arrangement, examples and questions are the original work of munotes.in.

   munotes.in is an independent study resource for MU students. It is not affiliated with, endorsed by, or officially connected to the University of Mumbai. Course names and university references describe the students and syllabus the material relates to.

   Contents

   Module I Introduction to Theory of Computation, Automata Theory, Formal Languages, Regular Languages and Context Free Languages

   1. What This Subject Is About, and the Four Questions It Answers 1
   2. Sets: The Vocabulary Everything Else Is Written In 6
   3. Alphabets, Strings and Languages 11
   4. Relations, and the Equivalence Relation That Runs Through This Subject 16
   5. Functions: What the Transition Function Actually Is 21
   6. Proof Techniques: Five Ways to Be Sure 25
   7. Counting the Uncountable: Diagonalisation, and Why Some Languages Have No Machine 30
   8. What an Automaton Is 35
   9. The Deterministic Finite Automaton, Formally 40
   10. Transitions and Their Properties: the Function, the Table and the Diagram 44
   11. The Extended Transition Function: What a Machine Does to a Whole String 49
   12. Acceptability: When a Machine Accepts a String, and What Language It Accepts 53
   13. Designing a DFA: the Method, and Eight Machines Built With It 58
   14. Nondeterminism, and the Nondeterministic Finite Automaton 64
   15. Empty Moves, and the Epsilon Closure 69
   16. DFA and NDFA Equivalence: the Subset Construction 73
   17. Removing the Empty Moves 79

   Contents continued

   Module I continued Introduction to Theory of Computation, Automata Theory, Formal Languages, Regular Languages and Context Free Languages

   1. Mealy and Moore Machines: a Machine That Writes 83
   2. Converting a Moore Machine to a Mealy Machine, and Back 87
   3. Minimizing Automata: the Partition Method 92
   4. The Myhill Nerode Theorem, and a Second Way to Prove a Language Not Regular 98
   5. What a Grammar Is 104
   6. Derivations: How a Grammar Makes a String 109
   7. The Language Generated by a Grammar, and Proving It Is the One You Claim 114
   8. Writing a Grammar for a Language You Are Given 119
   9. The Chomsky Classification of Grammars and Languages 124
   10. Recursive and Recursively Enumerable Sets 130
   11. Operations on Languages 135
   12. Languages and Automata: Which Machine Goes With Which Grammar 141
   13. Regular Grammar: the Right Linear and Left Linear Forms 146
   14. Regular Expressions 151
   15. The Identities of Regular Expressions 155
   16. Writing a Regular Expression for a Language You Are Given 160
   17. From a Regular Expression to a Finite Automaton 166

   Contents continued

   Module I continued Introduction to Theory of Computation, Automata Theory, Formal Languages, Regular Languages and Context Free Languages

   1. From a Finite Automaton to a Regular Expression: Arden's Theorem and State Elimination 171
   2. The Pumping Lemma for Regular Languages 177
   3. Applications of the Pumping Lemma 183
   4. Closure Properties of the Regular Languages 189
   5. The Decision Problems of the Regular Languages 195
   6. Regular Sets and Regular Grammar: Kleene's Theorem Assembled 200
   7. Context Free Grammars and Context Free Languages 204
   8. The Derivation Tree 208
   9. Leftmost and Rightmost Derivations 213
   10. Ambiguity of a Grammar 217
   11. Simplifying a Grammar, One: Useless Symbols 222
   12. Simplifying a Grammar, Two: Null Productions 227
   13. Simplifying a Grammar, Three: Unit Productions, and the Reduced Grammar 232
   14. Chomsky Normal Form 237
   15. Greibach Normal Form 242
   16. The Pumping Lemma for Context Free Languages 247
   17. Closure Properties and Decision Problems of the Context Free Languages 254

   Contents continued

   Module II Pushdown Automata, Linear Bound Automata, Turing Machines, and Computability and Complexity

   1. The Pushdown Automaton 261
   2. Instantaneous Descriptions and Moves 266
   3. Acceptance by a PDA: by Final State and by Empty Stack 271
   4. Designing a PDA: the Balanced Languages 276
   5. Designing a PDA: Palindromes, and Counting Two Things at Once 281
   6. The Deterministic Pushdown Automaton 287
   7. From a Context Free Grammar to a Pushdown Automaton 292
   8. From a Pushdown Automaton to a Context Free Grammar 297
   9. The Linear Bounded Automaton Model 302
   10. Linear Bounded Automata and the Context Sensitive Languages 307
   11. The Turing Machine 312
   12. Representations of a Turing Machine 317
   13. Acceptability by a Turing Machine: Accept, Reject and Loop 322
   14. Designing and Describing a Turing Machine 326
   15. Turing Machine Construction: Machines That Recognise 331
   16. Turing Machine Construction: Machines That Compute 336
   17. Variants of the Turing Machine: More Tapes, More Tracks, More Heads 341
   18. Variants of the Turing Machine: Nondeterministic, Offline, and the Enumerator 346

   Contents continued

   Module II continued Pushdown Automata, Linear Bound Automata, Turing Machines, and Computability and Complexity

   1. Recursive and Recursively Enumerable Languages 351
   2. Decidable and Undecidable, and What the Complement Tells You 355
   3. The Church Turing Thesis 359
   4. The Universal Turing Machine 364
   5. The Halting Problem 369
   6. Reduction: Proving a Second Problem Unsolvable 374
   7. Rice's Theorem 379
   8. The Post Correspondence Problem, and the Undecidable Problems of Grammars 384
   9. Time Complexity 389
   10. Space Complexity 393
   11. Big O Notation, and the Family Around It 397
   12. Class P 402
   13. Class NP, and the Certificate 406
   14. Polynomial Reductions 411
   15. NP Complete and NP Hard, and Cook's Theorem 417
   16. Proving a Problem NP Complete: Three Reductions Worked 423
   17. Complexity Hierarchies, and the P Against NP Question 429
   18. The Machines and the Grammars, Side by Side 434

   Page 1 onwards

   438 pages in this book. The cover and the contents are above. Everything from page one is in the pass.

   Notes

   2026 Edition, as per the latest syllabus. 438 pages.

   Every chapter in the notes: 87 chapters across 2 modules

   Module I Introduction to Theory of Computation, Automata Theory, Formal Languages, Regular Languages and Context Free Languages 51 chapters

   1. 1 What This Subject Is About, and the Four Questions It Answers pages 1–5
   2. 2 Sets: The Vocabulary Everything Else Is Written In pages 6–10
   3. 3 Alphabets, Strings and Languages pages 11–15
   4. 4 Relations, and the Equivalence Relation That Runs Through This Subject pages 16–20
   5. 5 Functions: What the Transition Function Actually Is pages 21–24
   6. 6 Proof Techniques: Five Ways to Be Sure pages 25–29
   7. 7 Counting the Uncountable: Diagonalisation, and Why Some Languages Have No Machine pages 30–34
   8. 8 What an Automaton Is pages 35–39
   9. 9 The Deterministic Finite Automaton, Formally pages 40–43
   10. 10 Transitions and Their Properties: the Function, the Table and the Diagram pages 44–48
   11. 11 The Extended Transition Function: What a Machine Does to a Whole String pages 49–52
   12. 12 Acceptability: When a Machine Accepts a String, and What Language It Accepts pages 53–57
   13. 13 Designing a DFA: the Method, and Eight Machines Built With It pages 58–63
   14. 14 Nondeterminism, and the Nondeterministic Finite Automaton pages 64–68
   15. 15 Empty Moves, and the Epsilon Closure pages 69–72
   16. 16 DFA and NDFA Equivalence: the Subset Construction pages 73–78
   17. 17 Removing the Empty Moves pages 79–82
   18. 18 Mealy and Moore Machines: a Machine That Writes pages 83–86
   19. 19 Converting a Moore Machine to a Mealy Machine, and Back pages 87–91
   20. 20 Minimizing Automata: the Partition Method pages 92–97
   21. 21 The Myhill Nerode Theorem, and a Second Way to Prove a Language Not Regular pages 98–103
   22. 22 What a Grammar Is pages 104–108
   23. 23 Derivations: How a Grammar Makes a String pages 109–113
   24. 24 The Language Generated by a Grammar, and Proving It Is the One You Claim pages 114–118
   25. 25 Writing a Grammar for a Language You Are Given pages 119–123
   26. 26 The Chomsky Classification of Grammars and Languages pages 124–129
   27. 27 Recursive and Recursively Enumerable Sets pages 130–134
   28. 28 Operations on Languages pages 135–140
   29. 29 Languages and Automata: Which Machine Goes With Which Grammar pages 141–145
   30. 30 Regular Grammar: the Right Linear and Left Linear Forms pages 146–150
   31. 31 Regular Expressions pages 151–154
   32. 32 The Identities of Regular Expressions pages 155–159
   33. 33 Writing a Regular Expression for a Language You Are Given pages 160–165
   34. 34 From a Regular Expression to a Finite Automaton pages 166–170
   35. 35 From a Finite Automaton to a Regular Expression: Arden's Theorem and State Elimination pages 171–176
   36. 36 The Pumping Lemma for Regular Languages pages 177–182
   37. 37 Applications of the Pumping Lemma pages 183–188
   38. 38 Closure Properties of the Regular Languages pages 189–194
   39. 39 The Decision Problems of the Regular Languages pages 195–199
   40. 40 Regular Sets and Regular Grammar: Kleene's Theorem Assembled pages 200–203
   41. 41 Context Free Grammars and Context Free Languages pages 204–207
   42. 42 The Derivation Tree pages 208–212
   43. 43 Leftmost and Rightmost Derivations pages 213–216
   44. 44 Ambiguity of a Grammar pages 217–221
   45. 45 Simplifying a Grammar, One: Useless Symbols pages 222–226
   46. 46 Simplifying a Grammar, Two: Null Productions pages 227–231
   47. 47 Simplifying a Grammar, Three: Unit Productions, and the Reduced Grammar pages 232–236
   48. 48 Chomsky Normal Form pages 237–241
   49. 49 Greibach Normal Form pages 242–246
   50. 50 The Pumping Lemma for Context Free Languages pages 247–253
   51. 51 Closure Properties and Decision Problems of the Context Free Languages pages 254–260

   Module II Pushdown Automata, Linear Bound Automata, Turing Machines, and Computability and Complexity 36 chapters

   1. 52 The Pushdown Automaton pages 261–265
   2. 53 Instantaneous Descriptions and Moves pages 266–270
   3. 54 Acceptance by a PDA: by Final State and by Empty Stack pages 271–275
   4. 55 Designing a PDA: the Balanced Languages pages 276–280
   5. 56 Designing a PDA: Palindromes, and Counting Two Things at Once pages 281–286
   6. 57 The Deterministic Pushdown Automaton pages 287–291
   7. 58 From a Context Free Grammar to a Pushdown Automaton pages 292–296
   8. 59 From a Pushdown Automaton to a Context Free Grammar pages 297–301
   9. 60 The Linear Bounded Automaton Model pages 302–306
   10. 61 Linear Bounded Automata and the Context Sensitive Languages pages 307–311
   11. 62 The Turing Machine pages 312–316
   12. 63 Representations of a Turing Machine pages 317–321
   13. 64 Acceptability by a Turing Machine: Accept, Reject and Loop pages 322–325
   14. 65 Designing and Describing a Turing Machine pages 326–330
   15. 66 Turing Machine Construction: Machines That Recognise pages 331–335
   16. 67 Turing Machine Construction: Machines That Compute pages 336–340
   17. 68 Variants of the Turing Machine: More Tapes, More Tracks, More Heads pages 341–345
   18. 69 Variants of the Turing Machine: Nondeterministic, Offline, and the Enumerator pages 346–350
   19. 70 Recursive and Recursively Enumerable Languages pages 351–354
   20. 71 Decidable and Undecidable, and What the Complement Tells You pages 355–358
   21. 72 The Church Turing Thesis pages 359–363
   22. 73 The Universal Turing Machine pages 364–368
   23. 74 The Halting Problem pages 369–373
   24. 75 Reduction: Proving a Second Problem Unsolvable pages 374–378
   25. 76 Rice's Theorem pages 379–383
   26. 77 The Post Correspondence Problem, and the Undecidable Problems of Grammars pages 384–388
   27. 78 Time Complexity pages 389–392
   28. 79 Space Complexity pages 393–396
   29. 80 Big O Notation, and the Family Around It pages 397–401
   30. 81 Class P pages 402–405
   31. 82 Class NP, and the Certificate pages 406–410
   32. 83 Polynomial Reductions pages 411–416
   33. 84 NP Complete and NP Hard, and Cook's Theorem pages 417–422
   34. 85 Proving a Problem NP Complete: Three Reductions Worked pages 423–428
   35. 86 Complexity Hierarchies, and the P Against NP Question pages 429–433
   36. 87 The Machines and the Grammars, Side by Side pages 434–438

5. Computer Science Practical 3

   Official Notes munotes.in

   Computer Science Practical 3

   B.SC. (COMPUTER SCIENCE) · SEMESTER 3

   Strictly as per the University of Mumbai NEP syllabus in force for B.Sc. (Computer Science)

   For B.Sc. (Computer Science) students of the University of Mumbai and all its affiliated colleges

   munotes.in Second Year

   Computer Science Practical 3

   Copyright © 2026 munotes.in. All rights reserved.

   Written and first published by munotes.in, 2026.

   This book is free for individual students to read at munotes.in. No part of it may be reproduced, distributed, stored, translated or used for institutional or classroom purposes in any form without a prior written licence from munotes.in.

   Licensing and permissions: contact@munotes.in

   The text of statutes and of judgments reproduced in this book is in the public domain under section 52(1)(q) of the Copyright Act 1957. The commentary, arrangement, examples and questions are the original work of munotes.in.

   munotes.in is an independent study resource for MU students. It is not affiliated with, endorsed by, or officially connected to the University of Mumbai. Course names and university references describe the students and syllabus the material relates to.

   Contents

   Module I Principles of Operating Systems: ten exercises in C on Linux

   1. How This Practical Is Examined: the Journal, the 80 Per Cent Rule and the Two Questions 1
   2. The Laboratory from Zero: gcc, a Program, and the Manual 6
   3. Processes: fork, wait, exec, and Why Two Programs Need to Talk 14
   4. Practical 1: Process Communication using Shared Memory 22
   5. Practical 1 continued: the Race Condition, Semaphores, and Producer and Consumer 31
   6. Practical 2: Process Communication with Pipes 40
   7. Practical 2 continued: Message Queues, Blocking and Non-blocking 48
   8. Practical 3: Threading and Single Thread Control Flow 57
   9. Practical 4: Multi-threading and Fibonacci Generation 67
   10. Practical 5: Process Synchronisation and the Bounded Buffer 77
   11. Practical 6: the Readers-Writers Problem 86
   12. Practical 7: CPU Scheduling, FCFS and Non-preemptive Scheduling 95
   13. Practical 8: CPU Scheduling, Round Robin 106
   14. Practical 9: Memory Management, FIFO and LRU Page Replacement 117
   15. Practical 10: Disk Scheduling 128
   16. Practical 10 continued: a Simple File System 137

   Contents continued

   Module II Data Structures: ten exercises in Python

   1. Python for Data Structures: the Tools This Module Uses 146
   2. Practical 11: Abstract Data Types and Custom Structures 154
   3. Practical 12: Singly Linked Lists 162
   4. Practical 13: Polynomial Operations Using Linked Lists 172
   5. Practical 14: Doubly Linked Lists 181
   6. Practical 15: the Stack ADT 190
   7. Practical 15 continued: Prefix to Postfix, and Evaluating It 198
   8. Practical 16: Queues and Circular Queues 207
   9. Practical 17: Binary Search Trees and Tree Traversals 217
   10. Practical 18: AVL Trees and Rebalancing 230
   11. Practical 18 continued: Heaps and Priority Queues 243
   12. Practical 19: Graph Representations and Traversals 258
   13. Practical 20: Hashing and Collision Handling 272

   Module J The journal and the practical examination

   1. Keeping the Journal, and What Goes on the Page 286
   2. A Worked Practical Paper: Q.1 and Q.2 293

   Page 1 onwards

   300 pages in this book. The cover and the contents are above. Everything from page one is in the pass.

   Notes

   2026 Edition, as per the latest syllabus. 300 pages.

   Every chapter in the notes: 31 chapters across 3 modules

   Module I Principles of Operating Systems: ten exercises in C on Linux 16 chapters

   1. 1 How This Practical Is Examined: the Journal, the 80 Per Cent Rule and the Two Questions pages 1–5
   2. 2 The Laboratory from Zero: gcc, a Program, and the Manual pages 6–13
   3. 3 Processes: fork, wait, exec, and Why Two Programs Need to Talk pages 14–21
   4. 4 Practical 1: Process Communication using Shared Memory pages 22–30
   5. 5 Practical 1 continued: the Race Condition, Semaphores, and Producer and Consumer pages 31–39
   6. 6 Practical 2: Process Communication with Pipes pages 40–47
   7. 7 Practical 2 continued: Message Queues, Blocking and Non-blocking pages 48–56
   8. 8 Practical 3: Threading and Single Thread Control Flow pages 57–66
   9. 9 Practical 4: Multi-threading and Fibonacci Generation pages 67–76
   10. 10 Practical 5: Process Synchronisation and the Bounded Buffer pages 77–85
   11. 11 Practical 6: the Readers-Writers Problem pages 86–94
   12. 12 Practical 7: CPU Scheduling, FCFS and Non-preemptive Scheduling pages 95–105
   13. 13 Practical 8: CPU Scheduling, Round Robin pages 106–116
   14. 14 Practical 9: Memory Management, FIFO and LRU Page Replacement pages 117–127
   15. 15 Practical 10: Disk Scheduling pages 128–136
   16. 16 Practical 10 continued: a Simple File System pages 137–145

   Module II Data Structures: ten exercises in Python 13 chapters

   1. 17 Python for Data Structures: the Tools This Module Uses pages 146–153
   2. 18 Practical 11: Abstract Data Types and Custom Structures pages 154–161
   3. 19 Practical 12: Singly Linked Lists pages 162–171
   4. 20 Practical 13: Polynomial Operations Using Linked Lists pages 172–180
   5. 21 Practical 14: Doubly Linked Lists pages 181–189
   6. 22 Practical 15: the Stack ADT pages 190–197
   7. 23 Practical 15 continued: Prefix to Postfix, and Evaluating It pages 198–206
   8. 24 Practical 16: Queues and Circular Queues pages 207–216
   9. 25 Practical 17: Binary Search Trees and Tree Traversals pages 217–229
   10. 26 Practical 18: AVL Trees and Rebalancing pages 230–242
   11. 27 Practical 18 continued: Heaps and Priority Queues pages 243–257
   12. 28 Practical 19: Graph Representations and Traversals pages 258–271
   13. 29 Practical 20: Hashing and Collision Handling pages 272–285

   Module J The journal and the practical examination 2 chapters

   1. 30 Keeping the Journal, and What Goes on the Page pages 286–292
   2. 31 A Worked Practical Paper: Q.1 and Q.2 pages 293–300

Questions