毕业后，Ullman 进入贝尔实验室工作，贝尔实验室是当时领先的计算机研究中心，他在那里继续发展在 SDC 度过暑假时获得的对形式语言理论的兴趣。三年后，他的第一本书《形式语言及其与自动机的关系》（Formal Languages and Their Relation to Automata）于 1969 年出版。这本书是与约翰-霍普克罗夫特（John Hopcroft）合著的，霍普克罗夫特因其在算法和数据结构方面的工作而获得了图灵奖。作为普林斯顿大学的新教员，霍普克罗夫特受邀为一小群研究生讲授计算机科学这一新兴领域的知识。乌尔曼就是其中之一，他后来与霍普克罗夫特合作，将课程材料扩展和延伸成一本书，成为计算机科学教育的主要内容。作为一门学科，计算机科学建立在数学、工程学和逻辑学等现有分支领域的理论和技术基础之上。这样的书籍对于整合这些以前分散的知识领域、以与计算研究相关的方式扩展这些知识领域，以及以连贯的方式向第一代接受计算机科学教育的学生展示这些知识领域至关重要。
他们早期在算法设计和分析技术方面的合作，为这一时期出现的计算机科学理论核心贡献了重要方法。这些算法工作侧重于处理图、字符串和序列的基本方法，与他们对编程语言的研究紧密结合在一起。他们与约翰-霍普克罗夫特（John Hopcroft）合作的奠基之作《计算机算法的设计与分析》（The Design and Analysis of Computer Algorithms）于 1974 年出版，这本书不仅为数十年来标准计算机科学课程中的算法教学，还为展示和分析研究界开发的新算法创建了概念框架。除了吸收他们自己的成果，该书还将一系列不同的算法编入一套通用的设计方法中，包括分而治之、递归、动态编程和其他早已进入计算机科学家标准工具箱的方法。