Code Complete by Steve McConnell : Chapter 8

The author recommends defining major data structures during requirements analysis and architecture phase.

The author then provides a data literacy test to identify what expertise the reader posses in understanding data structures. He also recommends reading some books if the reader is not an expert in data structures.

The author then enlists reasons to create own data types:

• Make modifications easier in future
• Avoid excessive information distribution
• Increase Reliability
• Compensate for language weaknesses
  

The author then provides guidelines for creating own data types:

• Create types with problem domain names
• Do not use predefined types (like int, float in C++) directly in the code except in type definitions
  
• Never redefine predefined types since it can create confusion in the mind of reader
• Define substitute types for portability
• Create types using other created types

The author then provides some guidelines for variable declarations:

• Use a template for variable declaration
• Turn of implicit declarations
• Use naming conventions

The author emphasizes the importance of data initialization. Improper initialization can result from several situations:

• A variable is never initialized
• A variable's value is outdated
• Only a part of the variable is assigned a value
  

The author then provides some guidelines for data initializations:

• Check input parameters for validity
• Initialize each variable close to where it is used
• Check the need for reinitialization
• Initialize named constants once, initialize variables with executable code
• Initialize each variable as it's declared
• Use compiler setting to initialize all variables
• Use compiler warnings for uninitialized variables
• Use a memory access checker to check for bad pointers
• Initialize working memory at the beginning of the program
  

Code Complete by Steve McConnell : Chapter 7

The author defines software design as a scheme of turning a specification of a computer program into an operational program. Design links requirements specification to coding and debugging. The author points out that design is a heuristic process and requires creativity and insight.

The author tries to distinguish between designs done in large and small projects. In large projects, design might be an activity distinct from requirements and coding and carried out by different set of people. The design may be divided in several stages like software architecture, high-level module design and detailed implementation design. Design work continues even after the design phase is over.

On small projects, design might involve just writing the PDL before coding it in the programming language.

The author then discusses design at different levels:

• Division into subsystems: This involves identification of major components in the software and interfaces/interaction between them.
  
• Division into modules: If a subsystem is too big to translate to module, this level ensures that the subsystem has been decomposed to a level of detail fine enough to implement it as a set of modules.
• Division into routines: This involves dividing a module into service routines and specifying syntactic details of service routines.
• Internal routine design: This requires writing PDL, investigating algorithms, deciding on organization of code and then coding in programming language.
  

The author then discusses two approaches of structured design:

• Top Down Decomposition: It is also called top-down design or stepwise refinement. It involves moving from a general statement of what the program does to detailed statements about specific tasks that are performed. Following steps should be followed in top down decomposition:
  
• Design top levels first before moving to lower levels
• Avoid language specific details
• Postpone details to lower level design
• Formalize and Verify each level
• Move to next level for next set of refinement

The author compares the technique with divide and conquer. The author advises to continue decomposition until it seems it is easier to code then decompose.

• Bottom Up Composition: Following steps need to be followed in bottom up decomposition:
• Identify low level capabilities from the description of the problem
• Identify common aspects of low level capabilities and group them
• Continue with the next level up

The author enlists following strengths of top-down approach:

1. It is easy
2. Implementation details can be deferred

Following weaknesses are also mentioned:

1. Systems not hierarchical in nature are difficult to design using this approach
2. This approach requires single function at the top which is different from modern event driven systems
3. Top level function of a system is hard to identify

The author provides following strengths of bottom-up approach:

1. It identifies utility routines early which results in compact design
2. It results in a lot of reuse

The following weaknesses of the bottom-up approach are mentioned:

1. This approach cannot be used exclusively. It needs to be combined with top-down approach.
2. Sometimes it becomes difficult to assemble pieces to build the system.
   

The author then discusses object-oriented design. The author defines the object-oriented design process as identification of real-world and abstract objects and representation of this objects by programming language objects. The author clarifies that object-oriented design works at a higher level of abstraction than structured design and the building of design is based on the data which makes it more stable approach.

The author then discusses following ideas related to object-oriented programming:

1. Abstraction: Object oriented design allows to ignore irrelevant details.
   The unit of abstraction in structured design is a function while in object-oriented design; it is an object. Since object has both functions and data, object-oriented design provides bigger intellectual building blocks than structured design.
   
2. Encapsulation: It involves principles of information hiding.
   
3. Modularity: It is nothing but grouping of related services and data into modules that are highly cohesive and loosely coupled.
   
4. Hierarchy and Inheritance: This involves identifying similarities and differences between different objects.
   
5. Objects and classes
   

The author provides following steps for object-oriented design:

• Identify objects and their attributes
• Determine what can be done to each object
• Determine what each object can do to other objects
• Determine parts of each object that will be visible
• Define each object's public interface
  

The author classifies objects in four main categories:

1. Problem Domain Component
2. User Interface Component
3. Task Management Component
4. Data Management Component
   

The author points out that without some object in each of these categories makes an incomplete design.

The author then compares following popular design approaches:

1. Structured Design: It works well for systems with several hundred lines of code.
   
2. Information Hiding: This approach should be used whenever possible.
   
3. Object Oriented Design: It works well for systems with more than hundred thousand to over a million lines of code.
   

The author suggests not to restrict to using only one approach. The author points out following three traits of the design process:

• Design is a sloppy process
  
• Design is a wicked problem
• Design is a heuristic process: The author provides reference to G Polya's book, How to Solve It and summarizes the approach that he suggested in his book.
  

When the design gets complete, it should have following characteristics:

1. Intellectual Manageability
2. Low Complexity
3. Ease of Maintenance
4. Minimal Connectedness
5. Extensibility
6. Reusability
7. High fan-in
8. Low to medium fan-out
9. Portability
10. Leannes
11. Stratified Design
12. Standard Techniques
    

Find depth of a k-ary tree given a parent array : Solution 1

The problem statement is mentioned here.

Following is the first solution.

initialize maxDepth to 0
for each node i from 0 to N-1
    set parent to P[i]
    set depth to 1
    while parent is not -1
       set parent to P[parent]
       increment depth
    end while
    if maxDepth < depth
       set maxDepth = depth
    end if
end for

As can be seen, the time complexity of the algorithm is $O(N^2)$ where $N$ is the number of nodes. The space complexity is $O(1)$.

Google Interview Question : Find depth of a k-ary tree given a parent array

Problem statement: You are given a k-ary tree with parent array $P$ such that $P[i], 0 \le i < N$ gives the parent of node $ i $ and $N$ is the total nodes in the tree. What is the time and space complexity of finding the depth of the tree?


Solution 1 and Solution 2 are available with $ O (n^2) $ complexity. Solution 3 gives $ O(n) $ algorithm.

Code Complete by Steve McConnell : Chapter 6

A module is a collection of data and the routines that act on the data. The author provides empirical evidence to prove that modularity contributes more to maintainability than structure does and is the most important factor in preventing corrective maintenance. Modular programming also improves maintainability and comprehension by programmers.

The author emphasizes on loose coupling of modules and strong cohesion among routines belonging to a single module.

The author then enlists the benefits of Information hiding such as:

1. Hide module level secrets: These include
• Data Structures
• Algorithms
• Areas that can change
• Hardware interaction
• Data size
• Input and Output
• Nonstandard language features
2. Ease of Modification: Changes are localized to routines of module when information is hidden from the rest of the program.
3. Better Readability:
   
4. Increased Reliability:
   

The author then enlists barriers that prevent usage of information hiding:

1. Excessive distribution of Information: If implementation of employee records as an array of 1000 elements is known to every part of the program, it deters use of information hiding.
2. Circular Dependencies among modules: If more than one modules are using the same set of data, the data would not be kept hidden from the rest of the modules.
   
3. Perceived performance penalties: The belief that information hiding will result into degrade in performance deters the use of information hiding.
   

The author then enlists some of the areas of a program around which modules can be created:

1. User Interface
2. Hardware Dependencies
3. System Dependencies
4. Data Management
5. Real world objects and abstract data types
6. Related Operations
7. Reusable Code

The author concludes the chapter showing the ways modules can be implemented in different programming languages.

Code Complete by Steve McConnell : Chapter 5

The author discusses a low-quality routine and enlists the problems associated with it which include:

• Bad name
• No documentation
• No error check on input data
• Use of magic numbers instead of constants
• Unused parameters
• Modification of global variables
• Too many parameters
• Poor parameter ordering

The author emphasizes importance of routines in computer science and discusses about reasons to create a routine:

• Reducing complexity: A routine hides information and makes it easier to manage complex programs.
• Minimize code size: Similar code at different places in the program can be put into a routine to reduce size of code.
• Improve correctness: Code in a routine is likely to be more correct since it is called with different inputs from several places.
  
• Improve maintainability: If a defect is discovered, the code needs to be changed at only one place.
• Limit effects of changes: Isolate areas that are likely to change in future.
• Hiding sequences: A routine hides the sequences of events and bundles them as a single operation.
• Improve performance: If a routine's performance is improved, many parts of the code benefit.
• Hiding implementation: A routine will hide implementation details of an operation be its data structures or algorithm.
  
• Promoting code reuse: Code in a routine can be reused in another program more easily.
• Improve readability: Putting a section of a code in a routine and giving it a proper name improves readability of the code where the routine is invoked.
• Improving portability: Use of routines isolate non-portable capabilities.

The author provides guidelines to create effective routine names:

• For a procedure, a verb followed by an object is a good combination, e.g. PrintReport, CheckOrder, etc... For Object Oriented languages, the object is not required in the name because it is already part of the procedure call, e.g. report.Print, order.Check, etc...
  
• For a function (which returns a value), the description of the return value should be used as the name, e.g. NextCustomer, CurrentPenColor, etc...

The author suggests to include everything that a routine does in a name and if the name becomes too long to describe everything it does, it should be broken in several parts. The author suggests that a good routine name has an average length of 15 to 20 characters against 9 to 15 for that of a good variable name.

The author enlists several types of acceptable and unacceptable cohesion in a routine as below:

• Acceptable
• Functional Cohesion: This occurs when a routine does one and only one operation.
• Sequential Cohesion: This occurs when a routine performs operations in a specific order sharing data from step to step and makes only a part of a bigger operation.
• Communicational Cohesion: This occurs when operations in a routine make use of the same set of data and aren't related in any other way.
  
• Temporal Cohesion: This occurs when operations are combined into a routine because they are all done at the same time.
• Unacceptable 
• Procedural Cohesion: This occurs when a routine performs operations in a specific order but the operations do not share any data.
  
• Logical Cohesion: This occurs when several operations are combined into a routine and one of the operations is selected by a control flag that is passed in.
• Coincidental Cohesion: This occurs when operations in a routine are not at all related.
  

The author discusses the idea of coupling. The degree of coupling between two routines describe the strength of connection between them. It is a complement to cohesion and it is better to have as loose coupling as possible. The author then discusses several parameters for coupling:

1. Size: Small routines with less number of parameters are loosely coupled compared to large ones or with lots of parameters.
2. Intimacy: The routines should try to interact directly through parameters and avoid interaction through indirect ways like global variables or database records.
   
3. Visibility: The connection between different routines should be prominent and not hidden.
4. Flexibility: It refers to how easily you can change the connections between routines.

The author gives examples of good and bad coupling.

1. Simple-data coupling: Two routines are simple-data coupled if all the data passed between them is non-structured and through a parameter list.
2. Data-structure coupling: Two routines are data-structure coupled if the data passed between them is structured.
3. Control coupling: Two routines are control coupled if one routine passes data to the other that tells the second routine what to do.
4. Content (Pathological) coupling: Two routine are pathologically coupled if one uses the code inside another or if one alters the local data used inside another.
   

The first two kind of coupling are acceptable while the last two are not.

The author then discusses about ideal length of a routine. Contrary to general belief, the author provides some empirical results to show that:

1. The size of routine is inversely proportinal to the number of errors per line of code. Small routines have more errors per line of code than larger routines.
2. Larger routines were cheaper to develop per line of code.
3. Code needed to be changed the least when routine averaged 100 to 150 lines of code.

But author still warns on writing routines larger than 200 lines of code since they become difficult to understand.

The author discusses about defensive programming, a technique where if a routine receives incorrect input, the behaviour of the routine is still defined and consistent. The author enlists several techniques of using defensive programming:

1. Assertions: The author suggests to use preprocessor macros for assertions and warns against putting executable code in assertions since the assertions may not execute in production code.
   
2. Check values of data input and routine parameters: Routines should be coded to verify the range of values for data obtained from a file or user and all the input parameters. A strategy should be in place on the software's behaviour on invalid data.
3. Exception Handling: Unexpected situations/errors should generate exceptions that becomes obvious in development and are recoverable in production code.
4. Change: Anticipate changes that can happen to a program and code in such a way that least number of routines get affected.
5. Function Return Values: Code should be written to always check function return values even if it will always be success.
   

The author then provides guidelines for function parameters:

1. Parameters should be in input-modify-output order.
2. If several functions have similar parameters, their orders should match.
3. Never have unused parameters.
4. Put status or error variable last.
5. Never change the routine parameters. Take a copy and operate on the copy.
6. Document assumptions about parameters
• Whether the parameter is input, modify or output
• Units (Millisecond, Inch, etc...)
• Range of expected values
• Special values used for error etc... that should never appear
• Meanings of status codes and error values
  
7. Limit the number of parameters to seven
8. Never assume any parameter passing mechanism (i.e. calling conventions)
   

The author ends the chapter with comments on issues of using macros and how to solve the issues.

Find Top N : Solution 3

The problem is described here. Solution 1 is here. Solution 2 is here. In both the earlier solution, we used some in-built function offered by IBM Lotus Domino XPages Server side Javascript. In this solution, I will just try to find the optimal solution theoretically without using any in-built functions.

In my MTech thesis, I had worked on multi-pattern matching algorithm, Aho-Corasick. The algorithm basically creates a finite state machine from a list of patterns that are to be searched in a document. A sample FSM created for input strings {he, him, his, she, her} is shown in the image to the left. If we modify the state machine in such a manner that it also keeps the count for a particular string in the end state, the machine can actually work for finding top-N strings from a list of strings.

Now about the time and space complexity, you can clearly see here that the time to create the state machine is $O(|S|)$ where $|S|$ is nothing but the cumulative length of all the strings together. In the second pass, we can keep a list of Top $N$ strings with their occurrence count and then go through each end state and insert/replace the string represented by that end state in the Top N strings list if the occurrence count is higher than any of the string inside the list. This second pass can take $O(|S| \times N)$. This makes it the optimal algorithm in terms of time complexity but space required is quite huge, to the tune of $O(|S|)$.

I thought there might be already some work in this area and found burstsort. This is the fastest sorting algorithm found till 2007 and uses trie. It was discovered by Ranjan Sinha. I found that the space requirement reduces a lot by using the technique mentioned in this algorithm. This is the optimal algorithm in terms of both time and space complexity.